Coins
-
유형
문제 요약
-
동적 프로그래밍, DP동전의 종류가 주어질 때, 동전을 교환할 수 있는 경우의 수를 구하세요.
※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
동전 교환 문제는 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";
}
}