[백준 2294] 동전 2 (DP) (C/C++) (★★)

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
//    freopen("B2294_input.txt", "r", stdin);
    
    int n, k;
    int dp[10010] = {0};
    int coin[10010];
    
    cin >> n >> k;
    
    for(int i = 0; i < n; i++)
    {
        cin >> coin[i]; 
    }
    
    for(int i = 0; i <= k; i++)
    {
        dp[i] = 99999999;
    }
    dp[0] = 0;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = coin[i]; j <= k; j++)
        {
            dp[j] = min(dp[j], dp[j-coin[i]] + 1);
        }
    }
    
    if(dp[k] == 99999999)
    {
        cout << "-1";
    }
    else
    {
        cout << dp[k];    
    }
    
    return 0;
}