(2293)(DP) 백준 동전1

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

풀이

---

n가지 종류의 서로 다른 값의 동전을 주고 각 동전들을 적당히 사용해서, 그 가치의 합이  k원이 되도록 할 때 총 경우의 수를 구하는 문제이다. 

각각의 동전은 몇개라도 사용해서 k원을 만들면 된다.

예를 들어서 coin[1] = 1, coin[2] = 2, coin[3] = 5 의 3가지 동전이 주어졌고 10을 만드는 총 경우의 수를 구해야 한다고 하면

먼저 1을 만들 수 있는 경우의 수부터 2를 만들 수 있는 경우 , 3, 4, .... 이런식으로 dp[j]에 coin[i] 순서대로 구해 저장 해놓기로 한다.

int dp[10001] = { 0 }; 

dp[0] = 1;

1을 만들 수 있는 경우 1  (1 가지) 1. dp[1] = dp[1] + dp[1 - coin[1]];

2를 만들 수 있는 경우 (1)-1 / 2 ( 1 + 1 가지) 2. dp[2] = dp[2] + dp[2 - coin[1]];     /   6.  dp[2] = dp[2] + dp[2 - coin[2]];

3을 만들 수 있는 경우 (1-1)-1 / (1)-2 (1 + 1 가지) 3. dp[3] = dp[3] + dp[3 - coin[1]];    /  7.  dp[3] = dp[3] + dp[3 - coin[2]];

4를 만들 수 있는 경우 (1-1-1)-1 / (1-1)-2 / (2)-2 (1 + 2 가지) 4. dp[4] = dp[4] + dp[4 - coin[1]];    /    8. dp[4] = dp[4] + dp[4 - coin[2]];

5를 만들 수 있는 경우 (1-1-1-1)-1 / (1-1-1)-2 / (1-2)-2 / 5 (1 + 2 + 1 가지) 5. dp[5] = dp[5] + dp[5 - coin[1]];    /    9. dp[5] = dp[5] + dp[5 -coin[2]];    /    10. dp[5] = dp[5] + dp[5 - coin[3]] ;

.

.

.

이런 식으로  순차적으로 dp를 구해주면 된다.

#include<stdio.h>
int main(){
int arr[101] = { 0 };
int dp[10001] = { 0 };
int N, K;
 
scanf("%d %d\n", &N, &K);
 
for(int i=1; i<=N; i++){
    scanf("%d", &arr[i]);
}
 
dp[0] = 1;
 
for(int i=1; i<=N; i++){
    for(int j=1; j<=K; j++){
        if(j >= arr[i]){
            dp[j] += dp[j - arr[i]];
        }
    }
}
 
printf("%d\n", dp[K]);
 
return 0;
}