백준 2624 - 동전 바꿔주기

www.acmicpc.net/problem/2624

 

각 고유한 가치를 지닌 동전의 개수가 주어졌을 때 금액 T를 만들 수 있는지, 가능하면 경우의 수가 몇 가지가 되는지 알아내는 문제이다.

 

2원이 4개 있다고 할 때 다음 테이블을 고려해보자.

 

금액	0	1	2	3	4	5	6	7	8
경우의 수	1	0	0	0	0	0	0	0	0

 

초기엔 0원을 만드는 경우도 인정하여 0원을 만드는 경우의 수를 1이라고 설정해 놓는다.

 

여기서 2원을 하나 가지고 테이블을 채워보자.

 

금액	0	1	2	3	4	5	6	7	8
경우의 수	1	0	1	0	0	0	0	0	0

 

자명하게도 1개의 2원 동전으로는 다음과 같이 테이블을 채울 수 있을 것이다.

 

여기서 2원을 하나 더 추가하면 다음과 같이 된다.

 

금액	0	1	2	3	4	5	6	7	8
경우의 수	1	0	1	0	1	0	0	0	0

 

마찬가지 방법으로 2원이 4개 있을 경우까지 고려하여 테이블을 완성할 수 있다.

 

금액	0	1	2	3	4	5	6	7	8
경우의 수	1	0	1	0	1	0	1	0	1

 

여기서 4원이 2개 있다고 하자.

 

4원 2개를 넣을 경우 테이블이 다음과 같이 변화할 것이다.

 

금액	0	1	2	3	4	5	6	7	8
경우의 수	1	0	1	0	2	0	2	0	2

 

아 이제 뭔가 보이는 것 같다. 0원을 채우는 경우의 수를 1로 정한 뒤, 동전을 하나씩 더해가며 가능한 경우의 수를 채우고 있다.

 

즉, 동전이 하나 추가되었을 때 지금까지 계산된 경우의 수를 더해주면서 테이블을 채울 수 있는 것이다.

 

따라서 점화식을 다음과 같이 정의할 수 있다.

 

n원일 때 계산하고 있는 동전의 가치를 v, 그 갯수를 c라 한다면 dp[n] += dp[n - v * c]

 

단, 금액을 오름차순으로 채우면 이미 해당 동전으로 이전에 계산이 된 테이블에 대해 중복으로 계산이 되므로 큰 금액부터 내림차순으로 테이블을 채워가도록 한다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int dp[10001];

int main()
{   
    dp[0] = 1;
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int val, typ;
    cin >> val >> typ;
    
    vector<pair<int, int>> coin(typ);
    
    for (int i = 0; i < typ; ++i)
    {
        int x, c;
        cin >> x >> c;
        coin[i] = {x, c};
    }
    
    for (int i = 0; i < typ; ++i)
    {
        int coin_val = coin[i].first;
        int coin_cnt = coin[i].second;
        
        for (int j = val; j >= 0; --j)
            for (int k = 1; k <= coin_cnt && j - coin_val * k >= 0; ++k)
                dp[j] += dp[j - coin_val * k];
    }
    
    cout << dp[val];
}

이해하기 쉽지 않았던 문제인 만큼 사람들이 이 글을 통해 영감을 얻었으면 좋겠다.