BOJ 백준 2294 : 동전 2

시작하면서

이번 문제는 다이나믹 프로그래밍(Dynamic Programming) 카테고리 문제이다.

BOJ 2294 - 동전 2

​

문제 이해

​ 이 문제에서 구해야하는 값은 “주어진 가치 k”의 값을 최소 개수의 동전으로 만드는 것이다. 문제를 해결하기 위해 어떤 값으로 dp 점화식을 만들건지 고민해야한다. 동전의 개수를 구해야하므로, k의 가치를 구할 때 필요한 동전의 개수를 구하는 식을 만들자.

1. dp 배열의 길이는 10,001로 잡는다(k의 최대 값이 10,000).

2. 우리는 동전의 개수를 최소로 찾아야하니 나올 수 없는 큰값(10,001)을 모든 dp 배열에 넣어준다.
3. dp[0]에는 0을 넣어준다. (나올 수 없는 값이므로)
4. dp[n] = min(dp[n], dp[n - coin] + 1) 점화식으로 dp 값들을 구한다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<int> coins;
	vector<int> dp;
	int n, k;

	cin >> n >> k;
	
	dp.resize(10001, 10001);
	dp[0] = 0;
	coins.resize(n);
	for (int i = 0; i < n; i++)
	{
		cin >> coins[i];

		for (int j = coins[i]; j <= k; j++)
		{
			dp[j] = min(dp[j], dp[j - coins[i]] + 1);
		}
	}
	
	cout << ((dp[k] == 10001) ? -1 : dp[k]);

	return 0;
}