[BOJ/백준] 2624: 동전 바꿔주기 (C++)

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

2624번: 동전 바꿔주기

 

[풀이] DP

 

dp 정의 : dp[n] = n원을 동전으로 교환하는 경우의 수.

 

 i : 0 ~ K-1까지 모든 동전 종류를 순회하면서

 i 번째 동전까지 썼을때의 dp[j] (j : T~1) 을 구해준다.

 

 T부터 거꾸로 하는 이유가 중요한데

1부터 할 경우 dp[1~j-1] 이 dp[j] 에 포함될 수 있기 때문이다.

dp[1~j-1]에는 i번째 동전을 쓰는 경우의 수까지 포함되어 있어서 dp[j]에는 포함되면 안된다.

       

동전 i를 몇개 선택할지 정해야 하기 때문에 동전 개수만큼 순회하면서 sum에 더해주고

if(j-sum >= 0 && dp[j-sum] > 0 을 만족하는 k를 찾으면 dp[j]에 dp[j-sum]을 더해주면 된다.

 

 

#include <cstdio>
 
int T, K, P[1001], cnt[1001],dp[10001];
 
int main() {
    scanf("%d%d", &T, &K);
    for (int i = 0; i < K; i++) scanf("%d%d", &P[i], &cnt[i]);
    dp[0] = 1;
    for (int i = 0; i < K; i++) {
        for (int j = T; j >= 1; j--) {
            int sum = 0;
            for (int k = 0; k < cnt[i]; k++) {
                sum += P[i];
                if (j - sum >= 0 && dp[j-sum] > 0) dp[j] += dp[j - sum];
            }
        }
    }
    printf("%d",dp[T]);
} 

 

https://github.com/has2/Algorithm/blob/master/boj/RANDOM_PROBLEM/2624.cpp