[다이나믹 프로그래밍] 백준 2624 - 동전 바꿔주기

백준 2624 - 동전 바꿔주기

입력으로 주어진 동전의 종류와 개수를 가지고 목표 금액을 만들 수 있는 조합의 개수를 구하는 문제! 자세한 설명은 아래 링크를 참조

💡 백준 2624 - 동전 바꿔주기

접근

1차 접근

우선, 입력의 개수가 크지 않습니다. 최대 100 * 1000개의 동전이 주어지죠. 완전탐색을 진행해도 무리없는 숫자라고 판단습니다. 큰 방법을 구상했으니, 세부 구현을 생각해볼 차례!

조합의 구성을 구하는 것이 아니라 단순히 개수만 구하면 됩니다. 따라서, DP처럼 배열에 개수만 저장하는 형태가 효율적이라고 판단했습니다. 구현 방법도 정했으니, 세부 구현을 할 차례.

완전탐색이고, DP 입니다. 따라서 N종류의 동전 중, 1~K번째 종류의 동전들을 이용해서 만들 수 있는 조합의 개수는 K-1번째 까지의 동전들을 가지고 만들 수 있는 조합의 개수들에서 K번째 동전의 값만큼 더하면 됩니다.

무슨말이냐 하면 ...

예를들어 5원짜리 3개로 만들 수 있는 조합은 0원, 5원, 10원, 15원 입니다. 배열의 인덱스가 금액이라고 하고 1을 더해줍니다.

dp[0] = 1
dp[5] = 1
dp[10] = 1
dp[15] = 1

이렇게 말이죠. 여기에서 다음 입력으로 10원 2개가 들어온다면?? 현재 dp 배열에서 0이 아닌 곳의 인덱스에서 10, 20을 더한 곳에 1을 더해주면 됩니다. dp[0] 이 1 이므로, dp[10] += dp[0] 이고 dp[20] += dp[0] 입니다. 이 과정을 dp 배열을 순회하면서 반복하면

dp[0] = 1
dp[5] = 1
dp[10] = 2
dp[15] = 2
dp[20] = 2
dp[25] = 2
dp[30] = 1
dp[35] = 1

이렇게 되어야 하죠... 그치만 문제가 발생합니다. 배열 하나에서 이렇게 진행하면, 0번 인덱스에서 진행한 결과가 바로 반영되어 10번, 20번째 인덱스에서도 또오 10과 20을 더하게 됩니다. 중복해서 더하는 꼴이죠.

2차 접근

자 문제점을 알았으니 방법을 바꿔봅니다. 값을 바로 반영하지 말고, 계산을 마친 후에 반영하면 해결되는 문제입니다. 따라서, dp라는 배열을 읽고 계산한 결과를 다른 배열에 저장하면 됩니다. 그 후, 계산 결과와 dp 배열의 값을 합치면 되는 것이죠.

최종 코드

#include <iostream>
#include <vector>
using namespace std;


int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int price;
    cin >> price;

    int types;
    cin >> types;

    vector<int> coins;
    vector<int> counts;
    vector<int> dp (price + 1, 0);
    vector<int> previous (price + 1, 0);
    dp[0] = 1;
    previous[0] = 1;

    int coin_price, coin_count;
    for (int i = 0; i < types; i++) {
        cin >> coin_price >> coin_count;
        coins.push_back(coin_price);
        counts.push_back(coin_count);
    }

    for (int i = 0; i < coins.size(); i++) {
        for (int x = 0; x <= price; x++) {
            if (previous[x] != 0) {
                for (int j = 1; j <= counts[i]; j++) {
                    if (x + coins[i] * j <= price) {
                        dp[x + coins[i] * j] += previous[x];
                    }
                }
            }
        }
        dp[0] = 0;
        for (int j = 1; j <= price; j++) {
            previous[j] += dp[j];
            dp[j] = 0;
        }
    }

    cout << previous[price] << endl;
    return 0;
}

중구난방처럼 설명했는데

그냥 이전 조합에서 현재 금액을 더하는 .... 그런 과정이었달까 ..