[백준 2294] 동전 2 (C++)

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

 

문제

---

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

 

입력

---

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

 

출력

---

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

 

문제 풀이

---

dp 문제.

i번째 동전의 가치가 A일 때 A * x원은 만들 수 있는 금액이며, 이 때 동전의 개수는 x개임을 이용한다.

만들려고 하는 가치의 합 j가 A보다 크다면 j를 A + α로 나누어 생각한다. 가치 A는 i번째 동전 1개로 만들 수 있으며, α는 dp를 이용하여 이전에 구한 값을 따른다. 따라서 dp[i][j] = dp[i][j-i]+1로 나타낼 수 있다. 또한 가치가 A인 i번째 동전을 쓰지 않고도 구할 수도 있는데, 이 경우는 dp[i][j] = dp[i][i-1]라는 식이 성립한다. 두가지 경우 중 사용한 동전의 개수가 더 적은 쪽의 개수를 따라 저장한다.

만들려고 하는 가치의 합 j가 A보다 작다면 i번째 동전을 사용하여 해당 금액을 만들 수 없다. 이전에 저장된 값을 그대로 사용한다. 따라서 dp[i][j]=dp[i-1][j]가 성립한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#define MAX 987654321
using namespace std;

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

	int N, K;
	cin >> N >> K;
	int* arr = new int[N];
	int** dp = new int*[N];
	for (int i = 0; i < N; i++)
	{
		dp[i] = new int[K+1];
		cin >> arr[i];
		dp[i][0] = 0;
		for (int j = 1; j < K+1; j++)
		{
			dp[i][j] = MAX;
		}
	}
	sort(arr, arr + N);
	for (int i = arr[0]; i < K+1; i += arr[0])
	{
		dp[0][i] = i / arr[0];
	}
	for (int i = 1; i < N; i++)
	{
		int currentMoney = arr[i];
		for (int j = 0; j < K + 1; j++)
		{
			if (j < currentMoney)
			{
				dp[i][j] = dp[i - 1][j];
			}
			else if (j % currentMoney == 0)
			{
				dp[i][j] = min(j / arr[i], dp[i-1][j]);
			}
			else
			{
				dp[i][j] = min(dp[i][j - currentMoney]+1, dp[i-1][j]);
			}
		}
	}
	if (dp[N - 1][K] == MAX)
	{
		cout << -1 << "\n";
	}
	else
	{
		cout << dp[N - 1][K] << "\n";
	}
	return 0;
}