[백준 2624] 동전 바꿔주기 (C++)

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

문제

---

명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

• 20 = 10×2 
• 20 = 10×1 + 5×2 
• 20 = 10×1 + 5×1 + 1×5 
• 20 = 5×3 + 1×5

입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법의 수는 231-1을 초과 하지 않는 것으로 가정한다.

 

입력

---

첫째 줄에는 지폐의 금액 T(0＜T ≤ 10,000), 둘째 줄에는 동전의 가지 수 k(0＜k ≤ 100), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 pi(0＜pi ≤ T)와 개수 ni(0＜ni ≤ 1,000)가 주어진다. pi와 ni사이에는 빈칸이 하나씩 있다.

 

출력

---

첫째 줄에 동전 교환 방법의 가지 수를 출력한다. 방법이 없을 때는 0을 출력한다.

 

문제 풀이

---

dp 문제.

 

동전을 한 가지만 사용한다면 동전의 금액이 p이고 개수가 n이라고 할 때, 금액이 p, p*2, p*3, ..., p*n일 때는 모두 가능한 가지 수가 1가지이고, 이 이외에는 0개이다. 여기에 금액이 q이고, 개수가 m인 동전을 사용한다고 한다면, 마찬가지로 금액이 q, q*2, q*3, ...q*m일 때 가능한 가지 수가 1 늘어난다. (q, q*2, q*3...이 p, p*2, p*3과 겹칠 수 있기 때문에 가지수가 1가지가 아니라 가능한 가지 수가 1 늘어난다고 표현한다.) 우리가 만들려는 금액이 t이고, 금액이 q인 동전을 1개 사용한다고 하면 금액이 q인 동전을 사용하지 않았을 때의 t - q 원의 가짓수를 가져올 수 있다. q인 동전 2개를 사용한다면 t-2*q원의 가짓수를 가져올 수 있다. q인 동전을 사용하지 않는다면 이전 t를 만드는 가짓수를 그대로 가져오면 된다.

 

즉, 2차원 dp 배열을 생성하고, 첫번째 동전의 배수 금액에 1을 채워넣는다. 이전 행의 데이터를 가져온 후(pi인 동전을 사용하지 않은 경우의 수), pi인 동전을 1개, 2개, ..., 사용한 경우의 수를 더해주면 되는데, 이는 금액이 dp[i][j]라고 할 때, dp[i-1][j - pi 동전을 x개 만큼 사용한 금액]으로 표현할 수 있다.

 

아래는 코드.

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

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

	int T, K;
	cin >> T;
	cin >> K;
	int** dp = new int*[K];
	pair<int, int>* arr = new pair<int, int>[K];
	for (int i = 0; i < K; i++)
	{
		dp[i] = new int[T + 1];
		cin >> arr[i].first >> arr[i].second;
		for (int j = 0; j < T + 1; j++)
		{
			dp[i][j] = 0;
		}
	}
	for (int i = 0; i < K; i++)
	{
		dp[i][0] = 1;
	}
	for (int i = arr[0].first; i <= min(arr[0].first * arr[0].second, T); i+=arr[0].first)
	{
		dp[0][i] = 1;
	}
	for (int i = 1; i < K; i++)
	{
		for (int j = 0; j < T + 1; j++)
		{
			dp[i][j] = dp[i-1][j];
			for (int k = arr[i].first; k <= min(arr[i].first * arr[i].second, j); k+= arr[i].first)
			{
				dp[i][j] += dp[i-1][j - k];
			}
		}
	}
	cout << dp[K - 1][T] << "\n";
	return 0;
}