[BOJ] 동전 2(2294)

[백준(BOJ)] 동전 2(2294) C++

문제 : BOJ_2294번 동전 2

문제 설명

DP

DP로 풀 수 있는 기본문제 동전 2입니다.

n 개의 동전이 주어지고, 동전마다 값이 주어집니다.

이때 동전들을 조합해서 주어진 k의 값을 최소한의 동전을 써서 맞춰야 합니다.

---

Solution

큰 동전이 항상 작은 동전의 배수임이 보장된다면 그리다 하게 풀 수 있지만,

위 문제는 동전끼리 서로 배수가 아닌 값 들이기 때문에 dp를 이용해 경우의 수를 다 봐줘야 합니다.

1원 ~ k 원을 확인하는 for 문안에 1 ~ n 번째 동전을 이용하는 for 문으로 2중 for 문이 필요합니다.

k는 최대 10,000이고 n은 최대 100이므로 최대 for 문이 1,000,000입니다.

동전을 확인할 때, 확인해야 하는 동전의 값과 최소한의 수를 확인해야 하는 값이 같다면 dp[값] = 1로 선언합니다.

동전의 값이 최소한의 수를 확인해야 하는 값보다 크다면 이용할 수 없으므로 넘어갑니다.

동전의 값이 최소한의 수를 확인해야 하는 값보다 작다면

dp[값] = min(dp[값], (dp[값 - 동전의 값] + dp[동전의 값]));

으로 해당 값의 최솟값을 계속 갱신해 줍니다.

---

Description

• 최솟값을 갱신하기 전 모두 INF 값으로 dp 값을 초기화해줍니다.
• 모든 for 문을 다 돌았는데도 INF 값과 dp 값이 같다면 동전으로 만들 수 없는 값입니다.
• k가 최대 10,000이므로, 10,001을 INF로 정했습니다.

---

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 100001
using namespace std;
vector<int> coinValue;
vector<int> dp;
int main(void) {
    int n, k;
    cin >> n >> k;
    dp.resize(k + 1);
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        coinValue.push_back(num);
    }
    for (int i = 1; i <= k; i++) dp[i] = INF;
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < n; j++) {
            if (coinValue[j] == i) dp[i] = 1;
            else if (coinValue[j] < i) {
                dp[i] = min(dp[i], (dp[i - coinValue[j]] + dp[coinValue[j]]));
            }
        }
    }
    if (dp[k] == INF) cout << -1 << '\n';
    else cout << dp[k] << '\n';
    return 0;
}