[BAE/<JOON> 문제풀이] 2993. 동전1 (DP.018)

폭풍저그머성찡 2020. 4. 28. 15:56

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

2293번: 동전 1

첫째 줄에 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<unsigned long> dp;
    coin.resize(n + 1);
    dp.resize(k + 1);    
    for (int i = 1; i <= n; i++) {
        cin >> coin[i];         
    }        
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {        
        for (int j = coin[i]; j <= k; j++) {
            //int val = (dp[i - 1][j] > dp[i][j - coin[i]] ? dp[i - 1][j] : dp[i][j - coin[i]]);
            dp[j] = dp[j] + dp[j - coin[i]];
        }
    }    
    /*for (int i = 1; i <= k; i++) {
        cout << dp[i] << " ";
    }*/
    cout << dp[k] << endl;
    return 0;
}