문제

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

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

---

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

---

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

문제 링크

풀이

동전1의 풀이와 마찬가지로 k원을 만들기 위한 최소 동전의 개수를 구하기 위해
k-동전의 값어치원을 만들기 위한 최소 동전의 개수가 필요하다.

점화식

• 0원을 만들기 위한 동전의 최소 개수는 0개이다
• f(k-coin)+1은 k-coin을 만들기 위한 최소 동전의 개수에서 자신의 값인 coin원 동전 1개를 더하여 k원을 만든 경우이다.

소지하고 있는 동전을 하나씩 사용하는 경우를 추가하며 k까지 값을 구한다.

코드

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

using namespace std;

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;
    vector<int> coins;
    vector<int> tabular(k+1, k+1);

    for (int i=0; i < n; i++){
        int coin;
        cin >> coin;
        coins.push_back(coin);
    }

    tabular[0] = 0;
    for(auto coin: coins){
        for (int i=1; i<k+1; i++){
            if ( i - coin >= 0 )
                tabular[i] = min(tabular[i], tabular[i-coin] + 1);
        }
    }
    
    if ( tabular[k]  == k+1) cout << -1 << endl;
    else cout << tabular[k] << endl;

    return 0;
}