[BAE/<JOON> 문제풀이] 2294. 동전 2 (DP.023)

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

2294번: 동전 2

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> coin;
    vector<int> dp;
    coin.resize(n + 1);
    dp.resize(k + 1);
    for (int i = 1; i <= n; i++) {
        cin >> coin[i];        
    }
    for (int i = 1; i <= k; i++) {
        dp[i] = 10000005;
    }
    dp[0] = 0;    
    for (int i = 1; i <= n; i++) {
        for (int j = coin[i]; j <= k; j++) {            
            if (dp[j] > dp[j - coin[i]] + 1) {
                dp[j] = dp[j - coin[i]] + 1;
            }
        }
    }
    /*for (auto d : dp) {
        cout << d << " ";
    }
    cout << endl;*/
    if (dp[k] == 10000005) {
        cout << -1;
        return 0;
    }
    cout << dp[k];
    return 0;
}