BOJ 2294번: 동전 2

문제

문제 바로가기> BOJ 2294번: 동전 2

2294번: 동전 2

풀이

dp[j] : 가치의 합 j를 만드는 데 사용한 동전의 최소 개수

 

1. j == coin[i] 인 경우,

동전 하나만으로 j를 만들 수 있으므로, dp[j] = 1

 

2. j > coin[i] 인 경우,

해당 동전을 사용해서 더 적은 동전으로 j를 만들 수 있는지, dp[j] = min(dp[j], dp[j-coin[i]]+1)

 

#include<iostream>
#define INF 987654321
using namespace std;

int n, k;
int coin[101], dp[10001];

void input(){
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> coin[i];
    for(int i=1; i<=k; i++) dp[i] = INF;
}

void solution(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            if(j == coin[i]) dp[j] = 1;
            if(j > coin[i]) dp[j] = min(dp[j], dp[j-coin[i]]+1);
        }
    }
    if(dp[k] == INF) cout << -1;
    else cout << dp[k]; // 사용한 동전의 최소 개수
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}