백준 2294 동전 2 (C++)

2294번: 동전 2

흔한 dp 문제이다. 최소 동전을 이용하여 합이 k가 되도록 만들어야 한다. dp는 dp[합] = 최소 개수를 나타낸다. 즉 dp[합] = min(dp[합], dp[합 - 동전] + 1)이 된다. 동전의 합으로 k를 나타낼 수 없다면 -1을 출력한다. 간단히 풀 수 있었던 문제였다. dp 유형이 점점 익숙해지는 것이 느껴진다.

#include <iostream>
#include <algorithm>

using namespace std;

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

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

    dp[0] = 0;

    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            if (i - value[j] < 0) continue;
            dp[i] = min(dp[i], dp[i - value[j]] + 1);
        }
    }

    if (dp[k] == 987654321) {
        cout << -1;
    }
    else {
        cout << dp[k];
    }
}

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

    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> value[i];
    }

    solution();

    return 0;
}