2624 - 동전 바꿔주기

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

작은 돈에 대해서 만들어질 수 있는 가지 수를 구하고, 그 가지 수들에 또 다른 동전을 추가하면 얼마나 더 만들 수 있는지를 추가하였다.

$dp$[$N$][$K$] = $N$번째 동전까지로 $K$원을 만들 수 있는 가지 수

N번째 동전마다, 이전의 K원에다가 (N번째 동전의 개수)만큼 더해보면서 반복하면 된다.
예를 들어, 입력이 아래와 같다면

10
3
3 2
5 1
1 3

1원으로 0, 1, 2, 3원을 1개씩 만들 수 있을 것이다. (최대 3개 사용)
여기에 3원을 0개 추가하면 0+0, 1+0, 2+0, 3+0원을 만들 수 있고, 1개 추가하면 3, 4, 5, 6원을. 2개 추가하면 6, 7, 8, 9원을 만들 수 있다.
이런식으로 각 단위마다 가지 수를 누적하면서 살피면 dp[N][만들고자 하는 돈] 에 정답이 들어있을 것이다.

위 예시의 정답은 1 (1원 2개, 3원 1개, 5원 1개) 이다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;

struct coins {
    int val, count;
    bool operator < (const coins& c) const {
        return val < c.val;
    }
} C[101];

int main(){
    int T, K;
    scanf("%d %d", &T, &K);
    for(int i=1; i<=K; ++i) scanf("%d %d", &C[i].val, &C[i].count);
    sort(C+1, C+K+1);
    int dp[101][10001]={};
    dp[0][0] = 1;
    for(int i=1; i<=K; ++i){
        for(int k=0; k<=C[i].count; ++k){
            for(int j=0; j<=T; ++j){
                if(j+C[i].val*k > T) break;
                dp[i][j+C[i].val*k] += dp[i-1][j];
            }
        }
    }
    printf("%d", dp[K][T]);
    return 0;
}