[백준] 2294: 동전 2

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

2294번: 동전 2

 

동전 1 문제는 금액을 만드는 경우의 수이고, 동전 2 문제는 금액을 만드는 경우 중 동전의 개수가 최소인 경우의 동전 수를 구하는 문제이다.

DP를 이용하여 해당 금액에 대한 최소 동전 개수를 저장하여 활용함으로써 정답을 찾을 수 있다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int n, k;
int coins[10004], dp[10004];
int main() {
    //1. 입력 받기
    cin >> n >> k;
    for (int i=0;i<n;i++){
        cin >> coins[i];
    } 
    //2. 동전의 경우의 수 구하기
    fill(dp, dp+10004, 10004);
    dp[0]=0;
    for(int i=0;i<n;i++){
        for(int j=coins[i];j<=k;j++){
            dp[j] = min(1 + dp[j-coins[i]], dp[j]);
        }
    }
    //3. 정답 출력
    if(dp[k]==10004) cout << -1 << "\n";
    else cout << dp[k];
    
    return 0;
}