2294-동전2

www.acmicpc.net/problem/2294

2294번: 동전 2

본 문제는 동전들이 주어지고, 각각의 동전에 대한 가치(원으로 생각)가 주어집니다. 그리고, 이 동전으로 k 원을 만들어낼 수 있는지, 만들어낼 수 있다면 주어진 동전을 최소 몇개를 써야 k원을 만들어낼 수 있는지를 묻는 문제입니다.

 

k원을 주어진 동전을 최소로 사용하여 만들기 위해서는 k원보다 작은 금액들을 먼저 최소로 사용하여 만들 수 있어야 합니다. 어떤 문제를 작은 문제로 분할하고 작은 문제를 해결해가며 문제를 해결한다. 즉, DP 기법을 사용해야 합니다.

 

테이블 dp가 있다고 가정하겠습니다. dp[i]의 값은 i 원을 만들기 위해 사용한 동전의 최소 개수입니다.

그리고, 주어진 n개의 동전들은 가치를 기준으로 오름차순으로 정렬되어 coins라는 벡터에 있다고 가정하겠습니다.

 

dp[0]의 값은 주어진 동전을 하나도 사용하지 않고 만들 수 있으므로 0입니다.

 

dp[coins[0]], dp[coins[1]], dp[coins[n-1]]의 값은 주어진 동전을 하나씩 사용하여 만들 수 있으므로 1입니다.

 

주어진 동전을 사용하여 t원을 만들 수 있을때, dp[t]의 값은 아래와 같이 정의될 수 있습니다.

 

dp[t] = min(1+dp[t-coins[0]], 1+dp[t-coins[1]], ..., 1+dp[t-coins[n-1]])

 

여기서, 더해지는 1은 coins[0], coins[1], coins[n-1]원 중 하나를 사용함으로써 추가되는 동전의 수입니다. t원을 만들기 위해 가지고 있는 동전 coins[0], coins[1], ..., coins[n-1] 중 하나를 사용했으니, dp[t-coins[0]], dp[t-coins[1]], dp[t-coins[n-1]] 중 가장 작은 값을 갖는 값에 1을 더하면 dp[t] 값이 됩니다.

코드

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

int n, k;
vector<int> coins;
int dp[100001] = {0, };

int main()
{
    //freopen("2294.txt", "r", stdin);
    cin >> n >> k;

    dp[0] = 0;
    for(int i = 1; i <= k; i++)dp[i] = 10001; //INT_MAX 오버플로 발생할 수 있음
    
    for(int i = 0; i < n; i++)
    {
        int coin;
        cin >> coin;

        coins.push_back(coin);
        dp[coin] = 1;
    }

    //동일한 가치를 갖는 동전 중복 제거
    sort(coins.begin(), coins.end());
    coins.erase(unique(coins.begin(), coins.end()), coins.end()); 

    if(k < coins[0])
    {
        cout << -1;
        return 0;
    }

    if(dp[k] == 1)
    {
        cout << 1;
        return 0;
    }

    for(int won = coins[0]; won <= k; won++)
        for(int coin:coins)
        {
            if(won-coin < 0) break;
            dp[won] = min(dp[won], 1 + dp[won-coin]);
        }

    if(dp[k]==10001) cout << -1;
    else cout << dp[k];

    return 0;
}