백준 2624 : 동전 바꿔주기

  개인적으로는 신선했는데 struct를 알고리즘 풀면서 처음 사용했기 때문이다. 뭐 어떻게 어떻게 하면 struct를 안쓰고도 문제를 풀 수 있었겠지만 struct를 사용함으로서 상당히 깨끗해진 것 같다. 그거 이외에는 다른 동전 문제, 냅색(knapsack) 문제와 동일한 것 같다.

---

  풀이

  언제나 그랬듯이 dp문제의 난이도는 dp로 사용할 배열을 얼마나 잘 정의하느냐에 달렸다. 나는 다음과 같이 정의했다.

 

dp[n][k] : n원을 k 단계까지의 동전을 사용해 만들 수 있는 경우의 수

 

  임의로 단계라는 말을 사용했는데 흔히 사용하는 level의 의미라기보다는 동전의 종류를 구분하기 위해 사용했다. 먼저 제시된 동전일수록 앞단계라고 생각했다. 따라서 예제로 제시된 '5원 동전 3개, 10원 동전 2개, 1원 동전 5개'에서는 5원 동전이 1단계, 10원 동전이 2단계, 1원 동전이 3단계인 것이다. 따라서 dp[10][2]이란 10원을 2단계까지의 동전(5원, 10원)을 사용해 만들 수 있는 경우의 수인 것이다.

 

  다음단계의 동전을 고려할 때 마다 이전 단계에서 화살표를 그려나간다고 생각하면 쉽게 이해할 수 있다. 예를 들어 다음 그림은 1단계에서 2단계로 넘어갈 때 10원짜리 동전을 사용하는 상황이다.

 

검정색은 0개의 동전을, 초록색은 1개의 동전을, 빨간색은 2개의 동전을 더한 선이다.

 

  10원짜리 동전이 총 2개 있으므로 동전을 0개 사용할수도, 1개 사용할수도, 2개 사용할수도 있다. 따라서 0단계에서 0이 아닌 값들에게 각각 경우를 화살표로 나타냈다. 목표 금액이 20원이기 때문에 금액이 20을 넘어가는 경우는 고려하지 않았다. 이와 같은 방식으로 모든 단계의 동전을 다 더해주면 된다.

 

#include <iostream>

using namespace std;

struct Coin
{
    int value;
    int count;
};

int total, k;
Coin coin[102];
int dp[10002][102];

int main()
{
    cin >> total >> k;

    for(int i = 1; i <= k; i++)
    {
        int v, c;
        cin >> v >> c;
        coin[i].value = v;
        coin[i].count = c;
    }
    
    for(int i = 1; i <= k; i++)
    {
        int v = coin[i].value;
        int c = coin[i].count;
        
        dp[0][i-1] = 1;
        for(int j = 0; j <= total; j++)
        {
            if(dp[j][i-1] == 0) continue;
            for(int n = 0; n <= c; n++)
            {
                if(j + n*v > total) continue;
                dp[j + n*v][i] += dp[j][i-1];
            }
        }
    }
    
    cout << dp[total][k];

    return 0;
}