[BOJ] C++ 9084: 동전 - DP의 핵심은 중복 제거!

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

9084번: 동전

예제

3
2
1 2
1000
3
1 5 10
100
2
5 7
22

ans :
501
121
1

---

주어진 n개의 동전으로 숫자 m을 만드는 방법의 수를 구하는 문제이다. 가장 먼저 떠오르는 방법은 역시 완전탐색이다. 최대 20개의 동전을 종류별로 다 더해주면서 계산하면 답이 나올 것 같긴 한데 굉장히 오래 걸리고 중복이 많이 발생할 것 같았다. 따라서 완전탐색은 안된다 생각하고 1, 2로 6을 만들어보면서 규칙을 찾아봤다.

 

6을 만드는 방법을 생각해보자. 6-1 = 5이므로 5를 만드는 방법에 1을 얹어주고 6-2 = 4이므로 4를 만드는 방법에 2를 얹어주면 된다. 이 방법은 이 전의 항을 사용하므로 dp로 가닥을 잡았다. dp로 가닥을 잡았다면 점화식을 생각해 보면 된다.

 

dp [i]를 i를 만드는 방법의 수로 하고, dp [m] += dp [m-coin [j]], j = 0~n-1로 점화식을 생각했다. 구현은 굉장히 쉬워서 그대로 구현하고 디버깅을 좀 해봤는데 이 점화식의 문제를 발견했다. 2+4와 4+2를 구하는 과정에서 중복이 발생한다는 점이었다. 내가 생각한 점화식대로 계산하면 2+4와 4+2는 동전의 순서만 바뀌고 같은 방식인데 다르게 카운팅 해서 이상한 답이 나온다. 그렇다면 중복을 제거해 주면 문제없이 작동할 것이다. 중복만 제거해 보자!

---

중복을 제거하는 방법은 순서를 좀 바꿔서 1로 만들 수 있는 dp 테이블을 쫙 채우고 다음 2로 채우는 방법이었다.

왜 이 방법이 중복을 제거하는지 아까의 예시에서 생각해 보자. 처음 동전 1로 테이블을 채우는 과정에서의 dp [6]은 2로 채우는 방법은 아직 고려하지 않은 상태이다. 즉, 1로만 6을 만드는 방법을 계산한 상태가 된다.

그리고 다음 동전 2로 테이블을 채우는데, 손으로 계산해 보면 중복이 발생하지 않는다. 이렇게 동작시키면 동전이 3개인 경우에도 중복이 발생하지 않는다.

중복을 제거하는 과정이 간단하면서도 떠올리기가 굉장히 힘들었다. 많은 연습이 필요할 것 같고 다음에 dp문제를 만나면 중복도 꼭 고려해 줘야겠다. 

/** DP 9084 동전 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        int coin[25], dp[10040];

        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> coin[i];
        cin >> m;

        fill(dp, dp + m + 1, 0);

        for (int i = 0; i < n; i++)
        {
            for (int j = coin[i]; j <= m; j++)
            {
                if (coin[i] == j)
                    dp[j]++;
                dp[j] += dp[j - coin[i]];
            }
        }

        cout << dp[m] << '\n';
    }
}