https://www.acmicpc.net/problem/2294
🔔 문제 :
(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];
}