[백준] 2624: 동전 바꿔주기

0. 문제 주소

 

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

2624번: 동전 바꿔주기

 

 

1. 풀이

 

[PS/DP] - [BOJ] 9084: 동전 참고

 

 

개수의 제한에 주의할 필요가 있다.

 

[PS/DP] - [BOJ] 9084: 동전에서는 단순히 이번 동전을 쓰냐 / 쓰지 않느냐 로 나누어 생각한 후,

 

메모이제이션을 통해 테이블들을 갱신해 나갔다.

 

하지만 개수의 제한이 있으므로, 이번 동전을 1개 썼을 때, 2개 썼을 때, ... 최대로 썼을 때의 경우를 모두 생각해야 한다.

 

 

그러므로 dp 테이블을 2차원으로 설계한 뒤,

 

dp[i][j] = i번째 동전까지 써서 j원을 만들 수 있는 경우의 수 로 저장을 하면 된다.

 

이를 구하기 위해서는, i번째 동전의 금액을 p_i, 개수 제한을 n_i라고 했을 때,

 

dp[i][j] = sum (k=1 to n_i) { dp[i-1][ j - k * p_i ] } 로 계산하면 된다.

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>
#define MAX 10005
#define pii pair<int, int>

using namespace std;

int T, K;
pii coins[105];
int dp[105][MAX];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d %d", &T, &K);
    for (int i=1;i<=K;i++){
        int p, n;
        scanf("%d %d", &p, &n);
        coins[i] = pii(p, n);
    }

    sort(coins+1, coins+K+1);


    for (int i=0;i<=K;i++){
        dp[i][0] = 1;
    }

    for (int i=1;i<=K;i++){
        int curr_coin = coins[i].first, curr_cnt = coins[i].second;
        for (int j=1;j<=T;j++){
            if (j < curr_coin){
                dp[i][j] = dp[i-1][j];
                continue;
            }
            for (int k=0;k<=curr_cnt;k++){
                if (j - k * curr_coin < 0) continue;
                dp[i][j] += dp[i-1][j - k * curr_coin];
            }
        }
    }

    printf("%d\n", dp[K][T]);
}