[백준 2293] 동전 1 [C]

백준 - 2293

---

풀이

가치가 n인 동전으로 k를 만드는 경우의 수는 k-n을 만드는 경우의 수와 같다. (단, k-n = 0의 경우의 수는 1로 설정)

ex) n = 2, 

k	1	2	3	4	5	6	7
경우의 수	0	1	0	1	0	1	0

가치가 n1, n2인 동전으로 k를 만드는 경우의 수는 "k-n을 만드는 경우의 수 + n1으로 k를 만드는 경우의 수"와 같다.

ex) n1 = 1, n2 = 2

k	1	2	3	4	5	6	7	8	9	10
n1	1	1	1	1	1	1	1	1	1	1
n2		2	2	3	3	4	4	5	5	6

이를 코드로 표현하면 다음과 같다.

for (int i = 0; i < n; i++)
    for (int j = coin[i]; j <= k; j++)
        dp[j] += dp[j - coin[i]];

---

소스코드

#include <stdio.h>
int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    int coin[n], dp[100001] = {1,};
    for (int i = 0; i < n; i++)
        scanf("%d", &coin[i]);
    for (int i = 0; i < n; i++)
        for (int j = coin[i]; j <= k; j++)
            dp[j] += dp[j - coin[i]];
    printf("%d", dp[k]);
}

---

출처

2293번: 동전 1