322. Coin Change

💡 풀이

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

  for (let i = 1; i < dp.length; i++) {
    for (let coin of coins) {
      if (i - coin >= 0) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }

  console.log(dp[dp.length - 1]);

  return dp[dp.length - 1] === Infinity ? -1 : dp[dp.length - 1];
};

// 아래는 규칙을 찾기 위해 몇 가지 적어둔 것이다.


// F(11) -> F(9) / F(8) / F(6)
// -> 만약 문제 예시처럼 11을 만들어야 한다면

// 9를 만드는 경우의 수, 8을 만드는 경우의 수, 6을 만드는 경우의 수(즉, 3가지 경우의 수 중에서 가장 작은 값을 구하면 된다.)의 최소값을 구하고, 거기에 '1을 더하면' cost 배열을 이용해 11을 만드는 경우의 수가 된다.

// 따라서 이를 식으로 표현하면
// F(11) = Math.min(F(9), F(8), F(6)) + 1

// 좀 더 자세히 표현하면
//F(n) = Math.min(F(n - cost[i]), F(n - cost[i + 1]), F(n - cost[i + 2])) + 1

// -> 위의 코드는 지금까지 작성했던 식을 코드로 표현한 것입니다.

let coins = [1, 2, 5];
let amount = 11;

coinChange(coins, amount);

📝 정리

마찬가지로 DP를 활용한 문제였다. 워낙 유명한 문제라 보자마자 Greedy로 풀어야 하는 줄 알고 DP를 생각하지 못했었는데, 규칙을 찾고 나니 DP로 해결하는 문제라는 것을 알게 됐다. 상세 풀이 설명은 위의 주석으로 대체하겠다.

수정, 지적을 환영합니다!

문제 링크

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

LeetCode GitHub

https://github.com/tTab1204/LeetCode