BOJ 9084 - 동전

BOJ 9084 - 동전

“다이나믹 프로그래밍”

BOJ 9084 - 동전

문제 링크


#include <bits/stdc++.h>
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;

int T;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); std::cout.tie(NULL);
    cin >> T;
    while (T--)
    {
        int N; cin >> N;
        int dp[10010];
        fill(dp, dp+10010, 0);
        vector<int>coins;
        for (int i = 0; i < N; i++) { 
            int coin; cin >> coin;
            coins.push_back(coin);
        } 
        int target; cin >> target;
        dp[0] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = coins[i]; j <= target; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        cout << dp[target] << '\n';
    }

    return 0;
}

  • 바킹독 dp 문제집에서 뽑았던 응용 문제이다. dp 문제라는 것을 알고 접근했는데도 점화식을 생각해내지 못했다. 컨셉 자체는 비슷하게 갔던 것 같은데, 생각이 끝까지 닿지 않았던 것 같다.

  • 딱 잘라 말했을 때, 점화식 부분은 아래와 같다.

for (int i = 0; i < N; i++) {
    for (int j = coins[i]; j <= target; j++) {
        dp[j] += dp[j - coins[i]];
    }
}
  • 가지고 있는 동전 배열의 각 동전 하나하나를 순회하면서(coins[0] ~ coins[N - 1]) 그 동전의 해당하는 값부터 시작하여 만들고자 하는 동전의 값(target)까지 해당 동전을 마지막으로 놓아서 값을 완성시키는 경우의 수를 헤아린다. 처음 들으면 난해할 수도 있는 설명이다. (이 부분을 알기 전까지 나는 dp[1000]이 dp[500]의 2배가 아닌지에 대해 생각하고 있었다.) 아래 그림을 보자.


  • 이것은 1원과 2원으로 1원부터 4원까지를 만드는 경우를 헤아려본 것이다(dp[1] ~ dp[4]를 채운다). dp[4]를 어떻게 유도할 수 있을까? dp 문제를 푼다는 관점으로 접근했을 때 가장 먼저 dp[2] + dp[3] 를 생각해볼 수 있을 것이다. dp[5]는? dp[3] + dp[4], dp[i]는? dp[i - 1] + dp[i - 2], k원과 k + 1원 으로 dp[N]을 유도한다면? dp[N - k] + dp[N - k + 1], 이런식으로 확장할 수 있을 것이다. 물론 이 계산은 정확하지 않다. dp[4]는 3인데, dp[2] + dp[3]는 4이고, 마찬가지로 헤아려보았을 때 dp[5]는 3인데, dp[3] + dp[4]는 5이다. 오차가 발생하는 것은 단순히 구하려는 타겟 값에 동전의 값을 빼기만 한 인덱스들의 합으로 만드는 점화식(예를 들어 위의 k원과 k + 1에 대한 N 만들기 식, dp[N] = dp[N - k] + dp[N - k + 1])에서 중복이 발생하기 때문이다.

  • 그러니까 dp[4]를 dp[2] + dp[3]으로 단순하게 처리할 경우, dp[4]에서 1 1 2로 4를 만드는 경우와 1 2 1로 만드는 수를 중복해서 세기 때문에 3개가 아니라 4개가 나오게 되는 것이다. 위의 점화식은 이러한 중복을 없애고 1로 끝나는 경우인 1 1 1 1, 2로 끝나는 경우인 1 1 2와 2 2를 정확하게 셀 수 있게 만들어준다. 딱 한번만 직접 반복문을 써보면 무슨 말인지 바로 알 수가 있을 것이다.