Algorithm/Algorithm 문제 풀이

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

폭풍저그머성찡 2020. 5. 2. 13:23

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

 

2294번: 동전 2

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

www.acmicpc.net

더보기 
#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;
}