[백준] 2294번: 동전2

2294번: 동전 2

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력

3 15
1
5
12

예제 출력

3

 

다른 다이나믹 프로그래밍 관련 문제들을 풀어왔다면, 꽤 쉽게 풀 수 있는 문제입니다. 풀이에서 dp 배열은 index를 만들 수 있는 최소 동전의 수를 담고 있는 배열입니다. 먼저 불가능한 케이스를 체크하기 위해 dp 배열을 -1로 초기화해줍니다. 

그리고 반복문을 돌면서, 이 동전의 크기만큼을 현재 index에서 빼줬을 때, 가능한 경우인지 체크, 가능한 경우라면 dp[i - arr[j]]에 1을 더한 (현재 동전을 더한다고 보면 됩니다.) 수가 현재 index에 저장되어 있는 수보다 작은지 체크해서 교체해줍니다.

이렇게 하면 자연스럽게 불가능할 때 dp[k]는 -1이 됩니다.

 

풀이에서 dp[0] = 0으로 설정되어 있는데요. i - arr[j] == 0인 경우는 동전의 크기와 index가 같은 경우로, dp[i] = 1이 되어야 하기 때문입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[101];
int dp[10001];

int main() {
    int n, k;
    cin >> n >> k;

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

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

    sort(arr, arr + n);

    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < n; j++) {
            if (i - arr[j] >= 0 && dp[i - arr[j]] != -1) {
                if (dp[i] == -1 || dp[i] > dp[i - arr[j]] + 1) {
                    dp[i] = dp[i - arr[j]] + 1;
                }
            }
        }
    }
    
    cout << dp[k] << '\n';
    
    return 0;
}