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

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

2294번: 동전 2

🔔 문제 : 

(1<= n <= 100)인 n가지 종류의 동전이 있습니다. 이를 사용하여

 

가치의 합이 (1 <= k <= 10,000)인 k의 값으로 만들고 싶습니다.

 

동전의 가치는 100,000보다 같거나 작은 자연수이며, 같은 동전이 여러 번 주어질 수도 있습니다.

 

이때, 사용한 동전의 최소 개수를 구하는 문제입니다.

---

🔔 Kick Point :

예를 들어 n=3, k = 10이며

동전이 2, 3, 5 라고 생각해보면

 

F(k) = min(F(k-2) + F(k-3) + F(k-5)) + 1  인 sub문제로 쪼갤 수 있습니다.

 

따라서 최솟값을 k값보다 높은 10001로 둔 후에

동전들을 비교해가며 dp[1]일때부터 dp[k]일때까지 bottom-up방식으로 채워나갔습니다.

 

이때 동전을 사용하지 못하는 경우는 -1로 둡니다.

   

---

🔔 Code :

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> coin(n);
	vector<int> dp(k + 1, 10001);
	dp[0] = 0;

	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}

	// O(n*k) Bottom-up
	for (int j = 1; j <= k; j++) {
		int min(10001);
		for (int i = 0; i < coin.size(); i++) {
			if ((j - coin[i] >= 0) && (dp[j-coin[i]] != -1) ) {
				min = (min > dp[j - coin[i]] ? dp[j - coin[i]] : min); 
			}
		}

		if (min == 10001) dp[j] = -1;
		else dp[j] = min + 1;
	}

	cout << dp[k];
}

---