https://www.acmicpc.net/problem/10431 10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 단순하게 생각하면 금방 풀 수 있다. 예를 들어 6 2 3 7 5 1 4 로 주어졌을 때, 각 학생이 옮겨지는 횟수는 자신보다 앞에 있는 수 중에서 자신보다 큰 수의 개수이다. 위의 예시로 봤을 때 다음 표와 같이 된다. 키 6 2 3 7 5 1 4 옮겨지는 횟수 0 1 1 0 2 5 3 여기서 옮겨지는 횟수를 모두 더하면 된다. 코드로 옮겨보면 간단하다. int cnt = 0; for (int i =..

https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 이 문제는 시간복잡도가 아주 중요한 문제이다. 단순하게 생각하면 금방 풀 수 있지만, 그러면 대다수는 시간복잡도에 걸린다. 내가 처음으로 제출한 코드는 다음과 같다. static void pro() { int deltaX = 1; int deltaY = 1; while (t-- > 0) { if (p == w) deltaX = -1; if (p == 0) deltaX = 1; i..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제의 조건 - 0과 1로만 이루어진 수를 이진수라고 한다. - 다음 조건을 만족하면 이친수라고 한다. 1. 이친수는 0으로 시작하지 않는다 2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. - N자리 이친수의 개수를 구하는 문제 d = [0]*91 n = int(input()) d[1] = 1 d[2] = 1 for i in range(..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 조건 - 인접한 자리의 차이가 1이 나는 수를 계단 수라고 한다. - 예 : 45656 - 길이가 N인 계단 수의 개수를 구하는 문제 D[i][j] = 길이가 i이고 마지막 숫자가 j인 계단 수의 개수 D[i][j] = D[i-1][j-1] + D[i-1][j+1] ( 1

https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 조건 - 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제 - 단 같은 수를 두 번 이상 연속해서 사용하면 안된다. - n=4 - 1+2+1 - 1+3 - 3+1 * 조건 때문에 점화식을 그대로 사용할 수 없다. -> 그 조건을 점화식에 넣기 D[i][j] = i를 1, 2, 3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j ... + 1 = i -> D[i][1] = D[i-1][2] + D[i-1][3] .....

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제의 조건 - 카드 N개를 구매해야 한다. - 카드팩은 총 N가지 종류가 존대한다. - i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i]원이다. - 카드 N개를 구매하는 비용의 최소값을 구하는 문제 n = int(input()) card = [0] card += list(map(int, input().split())) dp = [0 for _ in range(n+1)] dp[1] = car..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net [문제의 조건] 1. 카드 N개를 구매해야 한다. 2. 카드 팩은 총 N가지 종류가 존재한다. 3. i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i]이다. 4. 카드 N개를 구매하는 비용의 최대값을 구하는 문제이다. D[N] =카드 N개를 구매하는 최대 비용 = max(D[N-i] + P[i]) (1

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이 문제는 이전에 풀었던 11276 2*n 타일링 문제에서 조건이 추가된 문제이다. 이전에는 마지막에 두 가지 경우가 올 수 있었으나, 이 문제의 경우에는 세가지 경우가 올 수 있다. 그러므로 이 문제의 점화식은 D[n] = D[n-1] + D[n-2] * 2 이다. n = int(input()) D = [0 for _ in range(n+1)] if n == 1: print(n) elif n==2: print(n+1) els..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2*n 직사각형을 1*2, 2*1 타일로 채우는 방법의 수 D[n] = 2 X n 직사각형을 채우는 방법의 수 2*n 직사각형이 있을 때, 가장 오른 쪽에 타일을 놓을 수 있는 방법은 총 2가지가 있다. 1) 세로 블록이 하나 오는 경우 : D[n-1] 2) 가로 블록 두개 오는 경우 : D[n-2] D[n] = D[n-1] + D[n-2] 2*5의 경우 수는 (1) 2*3경우에서 블록 두 개를 더 붙이는 것과 (2)..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 큰 문제를 작은 문제를 통해 풀 수 있으므로 DP를 이용해 풀 수 있다. 예를 들어보면, 4가 입력 되었을 때 4 -> 2 -> 1 이므로 정답은 2가 된다. 이번에는 12가 입력된다면 12/3 = 4이므로 4를 입력으로 했을 때의 정답에서 1을 더하면 된다. 이와 같이 이 문제는 작은 문제들을 통해 큰 문제를 해결 할 수 있다. 또한 큰 문제를 작은 문제로 쪼갤 수 있다. D[N] = N을 1로 만드는 최소 연산 횟수 n = int(input()) dp = [0] * (n+1) dp[1] = 0 f..