2624-동전 바꿔주기

2624-동전 바꿔주기

동전1,2 문제보다 더 까다롭다고 생각하는 문제이다. 이 문제는 동전 1처럼 목표 금액을 만들 수 있는 경우의 수를 구하는 문제인데 차이점은 동전의 개수가 제한되어 있다는 점이다(동전1 문제는 동전의 개수가 무한대라고 가정했다). 따라서 동전1의 문제에서 살짝 꼬아서 낸 문제라고 생각하면 된다. dp테이블의 의미는 동전1과 동일하지만, 1차원이 아닌 2차원 배열이 필요하다. 그 이유는 곧 설명한다.

dp[a][b]=c : a번째 동전까지 봤을 때, b원을 만들 수 있는 경우의 수=c가지

아래의 코드에서 반복문의 변수 j가 바로 동전의 개수가 제한되어 있기 때문에 (동전1의 코드와 비교해서)새롭게 추가된 for loop이다. j는 최대 cnt[i]만큼 증가한다. 2차원 dp가 필요한 이유는 dp[i+1][]+=dp[i] 라는 식에서 볼 수 있듯이 현재 상태의 값은 이전 상태의 값에서 더해야 한다. dp[i]는 현재의 동전이 사용되지 않은 상태이기 때문이다. 단순 1차원 dp로는 개수 제한을 반영할 수 없다.

그리고 이 문제 역시 정렬할 필요가 없다(정렬을 앞으로도 계속 필요 없는듯).

#include<stdio.h>
int t, k, dp[101][10001];
int coin[101], cnt[101];
int main() {
    scanf("%d %d", &t, &k);
 
    for (int i = 0; i < k; i++)
        scanf("%d %d", &coin[i], &cnt[i]);
 
    dp[0][0] = 1;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j <= cnt[i]; j++) {
            for (int m = coin[i] * j; m <= t; m++) {
                dp[i + 1][m] += dp[i][m - coin[i] * j];
            }
        }
    }
 
    //동전1 문제의 코드와 비교
    //for (int i = 0; i < n; i++) {
    //    for (int j = coin[i]; j <= k; j++) {
    //        dp[j] += dp[j - coin[i]];
    //    }
    //}
    printf("%d\n", dp[k][t]);
    return 0;
}