백준_동전1

https://www.acmicpc.net/problem/2293

[ 풀이 법 ]

k원을 만드는 경우의 수는 아래의 그림과 같습니다.

[ 그림 1. k원을 만드는 경우의 수 ]

우선, 위의 배열은 어떤 금액을 만드는 경우의 수입니다. 배열이름을 dp라고 하겠습니다. 그러면 dp(k)는 k원을 만드는 경우의 수입니다. 그리고 Cn은 n번째 동전의 가치입니다. 위의 예제 입력에서 C1은 1, C2는 2, C3은 5입니다.

그럼, 이런 식의 점화식이 가능합니다. 

dp( n, k ) = dp( n, k - Cn ) + dp( n - 1, k )

이 점화식에서 dp( n, k )는 n개의 동전으로 k원을 만드는 경우의 수입니다. 그러므로 dp( n, k - Cn )은 n개의 동전으로 k - Cn을 만드는 경우의 수이고 dp( n - 1, k )는 n 번째 동전을 뺀 n - 1개의 동전으로 k원을 만드는 경우의 수 입니다.

위에서 세운 점화식을 dp(1, 1)부터 시작해서 dp(n, k)까지 반복했습니다. 이렇게 하면, dp(n, k)를 구할 수 있습니다. 당연히, dp(n, k)는 2차원 배열을 사용했고 이를 위해서, int dp[101][10001]처럼 배열을 선언했습니다. ( n의 최대값 100, k의 최대값 10000) 그런데, 이렇게 하면 메모리 초과가 나기 때문에 조금 꼼수가 필요했습니다. 위의 점화식을 보면 dp배열의 n번 째행과 n - 1번째 행만 필요합니다. 그래서 dp[2][10001]로 선언해서 문제를 풀었습니다.

마지막으로 초기 조건이 필요했습니다. 우선 배열을 dp[1][1]부터 채워 나가야 하는데, dp[1][1]이 무엇인지 위의 점화식으로 알 수 없습니다. 이를 구하기 위해서, 1행(dp[1][...])은 'C1으로 1원을 만들 수 있는 가?'를 의미하기 때문에 반복문을 돌면서 맞으면 1 아니면 0을 채웠습니다.

그 이후의 행은 dp[...][0] = 1, dp[...][-x] = 0을 조건으로 계산했습니다. 이 조건도 생각해보면 당연합니다. 금액이 0일 경우의 수는 하나도 안뽑는 경우 1개, 금액이 마이너일 경우는 당연히 없습니다.

[ 코드 ]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include <stdio.h>   int n, k; int coin[101], dp[2][10001];   int main() {     scanf("%d %d", &n, &k);     for(int i = 1; i <= n; i++)         scanf("%d", &coin[i]);       for(int tk = 1; tk <= k; tk++)     {         if(tk % coin[1] == 0)             dp[1][tk] = 1;     }       for(int tn = 2; tn <= n; tn++)     {         for(int tk = 1; tk <= k; tk++)             dp[0][tk] = dp[1][tk];         for(int tk = 1; tk <= k; tk++)         {             int pk = tk - coin[tn], pdp;               if(pk < 0) // k값이 음수인 경우는 없다.                 pdp = 0;             else if(pk == 0) // k값이 0이면 하나도 안뽑는 경우가 1개                 pdp = 1;             else    // 나머지는 dp에서 유추                 pdp = dp[1][pk];               dp[1][tk] = pdp + dp[0][tk];         }     }       printf("%d\n", dp[1][k]);     return 0; }