[Dynamic Programming][Medium] 322. Coin Change

https://leetcode.com/problems/coin-change/description

 

Q. 수 만큼 value인 coins 배열과 amount가 주어질때, coins에서 amount를 맞추기 위한 최소한의 동전수를 찾아라. 

 

Solution

 DP 계열의 좋은 문제. 

 

 동전을 치우면서 amount가 되면 과정의 수를 구하고, 그 중 최소를 찾는다. 

 많이 보는 패턴이다. 

 

 로직대로 코드를 만든다. 

 

 

int coin(vector<int>& vCache, vector<int>& coins, int amount)
{
    if(amount == 0) return 0;

    if(vCache[amount-1] >= 0)
        return vCache[amount-1];

    int minT = INT_MAX;
    for(int k = 0; k < coins.size(); ++k)
    {
        if(amount - coins[k] < 0) 
            continue;
        int ret = coin(vCache, coins, amount-coins[k]);
        if(ret != INT_MAX)
            minT = min(minT, 1 + ret);
    }
    return vCache[amount-1] = minT;
}

int coinChange(vector<int>& coins, int amount) 
{
    vector<int> vCache;
    vCache.resize(amount, -1);
    int ret = coin(vCache, coins, amount);
    return ret==INT_MAX ? -1 : ret;
}

 

적절한 결과.

 

 

Note 1) 캐시를 선택할 때에도 map/unordered_map 보다는 vector가 빠르다. 생각보다도 더 훨씬... 

Note 2) input coins를 먼저 sort 하고 loop에서 조건에 이탈하면 break 를 해 봤다. 결과는 이 경우 별차이 읍음....