[boj] 백준 2294 동전 2 (c++) - dp

[문제]

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

2294번: 동전 2

 

[풀이]

dp[k] = 가치의 합이 k가 되는 동전의 최소 개수를 저장한다.

가치가 i인 동전이 하나 있다면 (k의 가치 합을 만들 수 있는 동전의 개수)는 (k-i의 가치 합을 만들 수 있는 동전의 개수 + 1) 과 같이 생각할 수 있다. 

따라서 n개의 동전을 이용해서 그 동전의 가치~k 사이의 가치 합에 대해 더 적은 동전을 이용해 만들 수 있는지를 비교해서 dp 배열을 갱신해준다.  

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <math.h>
#define INF 987654321

using namespace std;

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //가치의 합이 k원이 되게 하는 동전의 최소 개수
    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin >> coin[i];
    }

    for(int i=1; i<=k; i++){
        dp[i] = INF;
    }

    //dp[i] = i의 가치를 만들 수 있는 동전의 최소 개수
    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]==INF)
        cout << "-1";
    else cout << dp[k];
}