📌 문제 설명

Coin Change 문제 보기

📌 문제 접근

문제 접근

처음에는 DFS로 풀면 안되나? 했는데, 그러면 너무 많은 경우의 수가 생길 것 같았다. 왜냐면 코인이 12개에, 양이 2^31-1 이기 때문이다. 따라서, DP로 풀면 되지 않을까? 라는 생각을 했다.

DP

DP는 작은 문제부터 풀어야하기 때문에 1부터 목표 금액까지 coin으로 만들 수 있는 금액만 확인하도록 구성하였다.

📌 내가 작성한 코드

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
const coinChange = (coins, amount) => {
  const answer = Array(amount + 1).fill(Infinity);
  answer[0] = 0;
  for (let i = 1; i < amount + 1; i++) {
    for (const coin of coins) {
      if (i - coin >= 0) {
        answer[i] = Math.min(answer[i], answer[i - coin] + 1);
      }
    }
  }
  return answer[amount] === Infinity ? -1 : answer[amount];
};

📌 시간 복잡도

O(amount * coins.length) - 각 금액마다 모든 동전을 확인하므로

📌 참고 링크

• Dynamic Programming - 위키백과