[BOJ] 2294. 동전 2

2294. 동전 2

1. 문제

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

2. 입력

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

3. 출력

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

4. 풀이

C++

#include <iostream>
#include <set>
using namespace std;
#define INF 10001

int n, k;
int dp[10001];

int main()
{
    cin >> n >> k;
    
    int value[100] = {0, };
    for (int i = 0; i < n; ++i)
        cin >> value[i]; 
    
    fill_n(dp, 10001, INF);
    dp[0] = 0;
    
    for (int i = 1; i <= k; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if ((i - value[j] >= 0) && (dp[i - value[j]] != INF))
            	dp[i] = min(dp[i], dp[i - value[j]] + 1);
        }
    }
    
    if (dp[k] != INF) cout << dp[k] << '\n';
    else cout << -1 << '\n';
}