[Algorithm] Baekjoon 2294번 : 동전 2

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

2294번: 동전 2

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, k, input;
    vector<int> coins;
    int dp[100001] = { 0 };
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
 
    cin >> n >> k;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
        coins.push_back(input);
    }
 
    sort(coins.begin(), coins.end());
    coins.erase(unique(coins.begin(), coins.end()), coins.end());
 
    for (int i = 0; i < coins.size(); ++i)
    {
        int curCoin = coins[i]; // 동전단위 선택.
 
        for (int j = curCoin; j <= k; ++j)
        {
            dp[j] = min(dp[j], dp[j-curCoin] + 1);
        }
    }
 
    if (dp[k] == 0x3f3f3f3f)
    {
        cout << -1;
        return 0;
    }
 
    cout << dp[k];
}
 
 

 

동전1 문제와 달리 사용되는 동전의 최소갯수를 구하는 문제이다.

마찬가지로 bottom up방식으로, 밑바닥부터 오차없이 값을 갱신해나가야 한다.

그전에 먼저 중복되는 동전단위가 들어올 수 있다고 하니, 정렬 후, 중복제거를 해줬다.

왜 굳이 이런 조건을 달아놨나 싶긴하다.

 

dp식이 제일 중요하니 해당 식을 보자.

dp[j] = min(dp[j], dp[j-curCoin] + 1;

 

curCoin은 현재 선택된 동전단위이다.

dp[12]에는 현재 선택된 동전단위까지를 활용한다고 했을 때, 12원을 만들기 위한 최소의 동전 갯수이다.

 

예를들어 1,5,12원짜리 동전중에서 5원짜리를 선택한 상태에서 dp[7]를 업데이트하려한다고 해보자.

먼저 dp[j-curCoin]+1에서, curCoin이 곧 +1이다. 즉, curCoin만큼 뺴줬다는건 해당동전을 사용했다는 것이고, 사용했기 때문에 +1을 해준것이다.

해당동전만큼의 돈을 빼줬기 때문에 7-5, dp[2], 즉 1,5원을 활용해서 2원을 만들기위한 최소의 동전갯수만 알아낸 후, 현재 동전을 사용한만큼인 +1을 해주면 된다.