[1일 1알고] G5 2294 동전 2

https://www.acmicpc.net/problem/2294

 

가장 기본적인 DP문제입니다.

예전에는 아이디어가 전혀 떠오르지 않았는데 이제는 생각나는게 신기하네요

 

n가지 동전을 통해 k원을 만드는 문제입니다.

배낭문제와 비슷하지만 해당 동전 문제는 같은 동전을 중복해서 사용할 수 있다는 차이점이 있습니다.

 

평범한 배낭 문제에서는 중복을 피하기 위해 뒤에서 앞으로 탐색했지만 동전 문제는 중복이 가능하기 때문에 앞에서 뒤로 탐색하는 것이 더 간편한 방법입니다.

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

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

    int N, K;
    cin >> N >> K;
    vector<int> coins(N, 0);

    vector<int> dp(K+1, 10001);
    for (int i = 0; i < N; ++i)
    {
        cin >> coins[i];
        if (coins[i] <= K)
            dp[coins[i]] = 1;
    }

    for (int i = 0; i <= K; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            int coin = coins[j];
            if (i - coin >= 0)
            {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    if (dp[K] == 10001) cout << -1;
    else cout << dp[K];
    return 0;
}

 

동전의 가치는 1이상이고 k는 최대 1만이기 때문에 10001로 미리 초기화 해놓았습니다.

 

불가능 한 경우에 -1를 출력하는 것과 i-coin이 인덱스를 침범하지 않도록 예외만 처리하면 쉽게 해결할 수 있는 문제였네요

---