Coins


작성일 : 2017-01-11 22:31:05
조회수 : 2829



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


동전 교환 문제는 Dynamic Programming으로 풀 수 있는 대표 유형격의 문제라고 볼 수 있습니다. 또한, 특수한 조건에서는 이 문제를 그리디로도 풀 수 있는데, 바로 동전들이 더 작은 동전의 배수로 주어지는 경우입니다.(ex : 1, 5, 10, 50, 100, 500)


그리디로 풀 수 있는 동전 교환문제는 당연히 DP로도 풀 수 있습니다. 배열을 돈의 최대 크기로 잡고, $dp[0]=1$ 로 값을 넣어줍니다. 동전문제는 이렇게 생각하시면 됩니다. 먼저 주어진 동전 액수만큼의 금액에는 경우의 수가 1이 추가됩니다. 그 다음, 그 금액부터 1원씩 증가시키면서, j번째 위치의 금액에 대해 $dp[j-coins[i]]$ 를 더하면 됩니다.


왜 이것이 성립할까요? 현재 2원짜리와 5원짜리가 있다고 해봅시다. 그러면 2원짜리로 2원을 만드는 방법 1가지가 먼저 존재합니다. 이 때 5원짜리 하나를 추가하게 되면 7원짜리를 만들 수 있게 되는데, 이 때 이 7원에 2원짜리의 경우의 수를 더하려면 $dp[7-5]$ 를 해야 합니다. 즉, 기존에 있던 금액에 현재 동전을 더한 경우를 더 추가한다고 생각하시면 됩니다.


아래 이미지는 구글링을 통해 얻은 동전 교환시 DP table의 상태를 표현합니다.


이 문제는 1차원, 2차원 배열 등으로 구현할 수 있지만, 소스코드에서는 1차원으로 구현한 소스를 올립니다.

#include<iostream>
using namespace std;

int main()
{
    int T;

    cin >> T;
    while (T--)
    {
        int n, w[20] = { 0 }, dp[10001] = { 0 }, m;
        
        cin >> n;
        for (int i = 0; i < n; i++) cin >> w[i];
        cin >> m;

        dp[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = w[i]; j <= m; j++)
                dp[j] += dp[j - w[i]];
        cout << dp[m] << "\n";
    }
}

Coins - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글