백준 2994 동전 2

algorithm  : dp

 

해설

dp[i] = 동전의 가치의 합이 i일때 최소동전의 갯수

 

#include<bits/stdc++.h>
#define LM 1000+10
#define INF 199999999
using LL = long long;
using namespace std;

int N,K;
int coin[LM];
int dp[100000 + 10];

void input(){
    scanf("%d %d",&N,&K);
    for(int i = 1 ; i <= N ; i++)
        scanf("%d",&coin[i]);
}

void DP(){
    for(int i = 1 ; i <= K ; i++) dp[i] = INF;

    for(int i = 1 ; i <= K ; i++){
        for(int j = 1 ; j <= N ; j++){
            if(coin[j] <= i)
                dp[i] = min(dp[i],dp[i - coin[j]] + 1);
        }
    }
    if(dp[K] == INF) printf("-1");
    else printf("%d",dp[K]);
}

int main(){
    //freopen("input.txt","r",stdin);
    input();
    DP();
    return 0;
}