백준 2294 (동전2)

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

해결 방법 : 동적 계획법

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int dp[10001]={0};
    int coin[101] = {0};
    int N,k;
    cin >> N >> k;
    
    for(int i = 1; i <= N; i++) cin >> coin[i];    
    for(int i = 1; i <=k; i++) dp[i] = 10001;
    
    
    for(int i = 1; i <= N; i++){
        for(int j = coin[i]; j <=k; j++)
            dp[j] = min(dp[j],dp[j-coin[i]] + 1);
    }
    
    dp[k] == 10001 ?cout << -1 : cout << dp[k];
}