← 9주차 · 그리디
보통DP

거스름돈

동전 종류가 담긴 배열 coins와 목표 금액 amount가 주어져요. 목표 금액을 만드는 데 필요한 동전의 최소 개수를 반환해요.

같은 동전을 여러 번 사용할 수 있어요. 어떤 조합으로도 금액을 만들 수 없다면 -1을 반환해요.

탐욕적으로 큰 동전부터 쓰는 방법은 틀려요. 예를 들어 coins = [1, 3, 4], amount = 6이면 4+1+1(3개)이 아니라 3+3(2개)이 정답이에요.

예시

예시 1
입력
coins = [1, 2, 5], amount = 11
출력
3
설명
11 = 5 + 5 + 1 이므로 3개예요.
예시 2
입력
coins = [2], amount = 3
출력
-1
설명
2원짜리로는 3원을 만들 수 없어요.
예시 3
입력
coins = [1], amount = 0
출력
0

제한 사항

  • 1 ≤ coins.length ≤ 12
  • 1 ≤ coins[i] ≤ 2^31 - 1
  • 0 ≤ amount ≤ 10,000
dp[i] = i원을 만드는 최소 동전 개수로 둬요. dp[0] = 0이고, 각 금액 i마다 모든 동전 c에 대해 dp[i] = min(dp[i], dp[i - c] + 1) 이에요.
javascript
function coinChange(coins, amount) {
  const INF = Infinity;
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i && dp[i - c] + 1 < dp[i]) {
        dp[i] = dp[i - c] + 1;
      }
    }
  }
  return dp[amount] === INF ? -1 : dp[amount];
}
이전 문제구명보트
다음 문제올바른 괄호
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.