[75 LeetCode] 13 - Coin Change

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/coin-change/description/

Coin Change - LeetCode

 

몇년전에 비슷한 유형을 분명 풀어봤었는데, 안 보다 보니 결국 원했던 방식의 답을 찾지 못했다.

처음엔 너무 그리디처럼 보여서 그리디로 풀었는데 정답이 아니었다.

생각해보니 바로 반례가 떠올랐다.

그래서 탐색을 해야하는구나 싶어 dfs를 사용해봤다.

dfs로 풀면 다음과 같다.

푸는 내내 점화식이 떠올랐는데, dfs외의 구현이 떠오르지를 않았다.

https://leetcode.com/problems/coin-change/editorial/
위 에디토리얼을 좀 학습할 필요가 있다.

1. Brute Force

2. DP (Top-down) (내 구현)

var coinChange = function(coins, amount) {
  const cache = new Map();

  coins.sort((a, b) => b - a);

  for (let coin of coins) {
      cache.set(coin, 1);
  }

  return dfs(coins, amount, 0, cache);
};

const dfs = (coins, amount, idx, cache) => {
  if (cache.get(amount)) return cache.get(amount);
  if (amount  < 0) return -1;
  if (amount  === 0) return 0;

  let minCount = -1;

  for(let i = 0; i < coins.length; i++) {
      const res = dfs(coins, amount - coins[i], i, cache);

      if (res >= 0) {
          minCount = minCount >= 0 ? Math.min(minCount, res + 1) : res + 1;
      }
  }
  cache.set(amount, minCount);
  return minCount;
}

3. DP (Bottom-up)

amount가 k일 때 가능한 최소값을 dp(k)라 하면, dp(1) ~ dp(amount) 값을 아래부터 위로 계산해 나간다.

첫 번째 coin만 사용할 수 있는 경우부터 코인을 하나씩 늘려가며 dp를 최신화해주는 방법이다.

1. 1번 코인으로 만들 수 있으면 dp[i] = i / (1번 코인의 값)
2. 1번과 2번 코인으로 만들 수 있으면 (2번만 사용해도 됨) 마찬가지로 진행
...
n. 반복하면 원하는 값 (dp[amount])는 모든 코인으로 만들 수 있는 방법 중 최소의 값이 된다.

Top-down 방식과 시간복잡도는 같은데, (O(S*n)) (S: amount, n: coin의 개수)
iteration을 통해 문제를 해결해서 훨씬 빠른 결과가 나오는 것 같다.

var coinChange = function(coins, amount) {
    const dp = new Array(amount +1).fill(Infinity);
    dp[0] = 0;

    for(let i =0; i<coins.length; i++){
        for(let j = coins[i]; j<=amount; j++){
            dp[j] = Math.min(dp[j], dp[j - coins[i]] +1)
        }
    }
    return dp[amount] == Infinity ? -1 : dp[amount]
};