[Baekjoon/C++] 2294번 - 동전 2

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

 

입력

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

 

출력

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

 

---

풀이

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

unordered_set<int> coins;
vector<int> dp(10001, -1);

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

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;

        dp[num] = 1;
        coins.insert(num);
    }

    for (int i = 1; i <= k; i++) {
        if (dp[i] > 0) {
            for (int coin : coins) {
                int idx = coin + i;
                
                // 범위 제한
                if (idx > 10000) continue;
                
                // 사용 동전의 최소 개수 갱신
                if (dp[idx] == -1)
                    dp[idx] = dp[i] + 1;
                else
                    dp[i + coin] = min(dp[i] + 1, dp[i + coin]);
            }
        }
    }

    cout << dp[k] << '\n';

    return 0;
}

 동전의 가치는 중복되어서 입력될 수 있고, 이 가치가 정렬되어 있을 필요성이 없기 때문에 unordered_set에 coin의 가치를 입력 받았다. 해당 동전과 같은 값들은 동전 하나로 표현할 수 있기에 dp[num]을 1로 초기화하도록 했다.

 

    for (int i = 1; i <= k; i++) {
        if (dp[i] > 0) {
            for (int coin : coins) {
                int idx = coin + i;
                
                // 범위 제한
                if (idx > 10000) continue;
                
                // 사용 동전의 최소 개수 갱신
                if (dp[idx] == -1)
                    dp[idx] = dp[i] + 1;
                else
                    dp[i + coin] = min(dp[i] + 1, dp[i + coin]);
            }
        }
    }

    cout << dp[k] << '\n';

 다이나믹 프로그래밍으로 각 값들을 표현하기 위해 필요한 동전의 수를 구하는 부분의 코드이다.

 1원부터 k원까지 쭉 살펴보다가 dp[i]가 0보다 크다면 i는 동전으로 표현할 수 있는 값이다. i를 동전으로 표현할 수 있다면 i + (동전의 가치) 또한 동전으로 표현할 수 있다. 그렇기에 for문으로 i + (동전의 가치)에 필요한 동전의 수를 갱신하도록 했다. 이때 idx가 범위를 넘어갈 수도 있으므로 if문으로 범위 초과를 방지했다.