Boj 2294 c++ 동전2

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

 

N개의 동전이 있다. 이 동전들을 적절히 사용하여 K원을 만들고자 한다.

이때, 동전들을 최소로 사용하는 경우를 출력하는 것이 문제이다. 

K원을 만들 수 없는 경우에는 -1을 출력한다.

 

결론부터 말하자면 자력솔에 성공하였다....! 

전날에 냅색을 풀었던 덕분인지 풀이법이 곧바로 생각났다.

 

풀이를 요약하자면 일차원 dp의 이중 for문 갱신이다. 

 

dp배열의 정의는 'i원을 만들 수 있는 동전의 최소 개수'이다.

이 경우, min을 사용해야 하기에 전날에 배웠던  inf 초기화를 해주어야 한다.

이 과정을 거치면 갱신을 거친 후에도 값이 inf로 남아있으면 -1을 출력하면 되기에 답을 구하는데에 매우 용이하다(k원을 만들 수 있는 경우가 존재하지 않는다는 뜻이기 때문)

하지만 dp[0]은 0으로 초기화 해주는 것 또한 기억해야 한다.

 

점화식의 형태는  전형적인 냅색의 형식이다.

dp[j] = min(dp[j], dp[j-coin] + 1)

해당 동전을 선택한 경우와 선택하지 않은 경우 모두를 고려하여 하나의 동전씩 배열의 값들을 갱신해나가는 것이다.

 

전체코드는 다음과 같다.

#include <iostream>
#define Max 1000001
using namespace std;

int dp[10001];
int coin[101];

int main() {

    int n, k;

    cin >> n >> k;

    for(int i = 1; i <= n; i++) {
        cin >> coin[i];
    }
    for(int i = 0; i <= 10000; i++) {
        dp[i] = Max;
    }
    dp[0] = 0;
    for(int i = 1; i <=n; i++) {
        for(int j = coin[i]; j <= k; j++) {
            dp[j] = min(dp[j], dp[j-coin[i]] + 1);
        }
    }
    if(dp[k] == Max) {
        cout << "-1";
        return 0;
    }
    cout << dp[k];

}