[백준] 2294번 동전 2 C++ 코드

코드

#include <iostream>

using namespace std;

int n,k,a[103],dp[10003];

int main() {
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    fill(dp, dp + 10003, 987654321); // 최소 개수를 찾아야 해서 큰 값으로 초기화
    dp[0] = 0; // 0원을 만들 때 필요한 동전의 개수는 0개
    for(int i = 0; i < n; i++) {
        for(int j = a[i]; j <= k; j++) {
            dp[j] = min(dp[j], 1 + dp[j - a[i]]);
        }
    }
    cout << (dp[k] == 987654321 ? -1 : dp[k]) << '\n';
    return 0;
}

풀이

j원을 만들 때 필요한 동전의 개수 구하기 문제이다. dp[j]는 현재까지 구한 j원을 만드는 최소 동전 개수이다. dp[j - a[i]] + 1은 j - a[i]원을 만드는 최소 동전 개수에 a[i] 동전을 추가한 것이다. 따라서, dp[j]는 dp[j]와 dp[j - a[i]] + 1 중 작은 값으로 갱신된다.