동전 교환 — 최소 개수·경우의 수

`dp[금액]`을 작은 금액부터 채워요. 각 동전을 빼 보며 최소 개수나 경우의 수를 구해요.

이럴 때 써요

정해진 단위들로 목표 금액을 만드는 데 필요한 최소 개수를 구할 때
목표 금액을 만드는 경우의 수(조합)를 셀 때
단위(동전·우표·묶음)를 여러 번 써도 되고, 합을 딱 맞춰야 할 때
그리디로 큰 단위부터 집어도 최적이 안 나올 것 같을 때

개념

동전 종류가 주어지고 각 동전은 몇 번이든 쓸 수 있어요. 목표 금액을 만드는 문제인데, 두 갈래가 있어요. 최소 개수 — 금액을 만드는 데 필요한 동전 수를 최소로. 경우의 수 — 금액을 만드는 서로 다른 방법이 몇 가지인지. 둘 다 dp[a]를 금액 a에 대한 답으로 두고 작은 금액부터 채워요.

최소 동전 수

dp[a]를 금액 a를 만드는 최소 동전 수로 정의해요. 금액 a를 만들려면 마지막에 어떤 동전 coin을 하나 놓았다고 보고, 그 전 금액 a - coin의 최선에 1을 더해요. 모든 동전을 시도해 가장 작은 걸 골라요. dp[a] = min(dp[a], dp[a - coin] + 1). 아직 못 만드는 금액은 Infinity로 둬요.

"동전 [1, 2, 5], 금액 11의 최소 개수"
dp[0] = 0   (0원은 0개)
나머지는 Infinity 로 시작해요
dp[1] = 1     (1)
dp[2] = 1     (2)
dp[3] = 2     (1+2)
dp[4] = 2     (2+2)
dp[5] = 1     (5)
dp[6] = 2     (5+1)
dp[7] = 2     (5+2)
dp[8] = 3     (5+2+1)
dp[9] = 3     (5+2+2)
dp[10] = 2    (5+5)
dp[11] = 3    (5+5+1)
답: dp[11] = 3

만드는 경우의 수

dp[a]를 금액 a를 만드는 방법의 수로 바꾸면, 어떤 동전으로 금액 a를 완성하는 방법은 a - coin을 만드는 방법 수만큼 있어요. 그래서 dp[a] += dp[a - coin]. 시작값은 dp[0] = 1이에요(아무것도 안 쓰는 방법 한 가지).

그리디(큰 동전부터 욕심껏)가 항상 되진 않아요. 동전이 [1, 3, 4]이고 금액이 6이면, 그리디는 4 + 1 + 1 = 3개를 고르지만 최적은 3 + 3 = 2개예요. 임의 단위에선 DP가 안전해요.

패턴 코드

최소 동전 수못 만드는 금액은 Infinity로 두고, 전이할 때 dp[a - coin]이 유효할 때만 후보로 삼아요. 끝까지 Infinity면 만들 수 없다는 뜻이라 -1을 돌려줘요.

javascript
Copy code
function coinChangeMin(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 0원은 동전 0개
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a && dp[a - coin] !== Infinity) {
        dp[a] = Math.min(dp[a], dp[a - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

만드는 경우의 수(조합)동전 루프를 바깥에 둬야 순서를 무시한 조합으로 세요. dp[0] = 1에서 출발해요.

javascript
Copy code
function coinChangeWays(coins, amount) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1; // 0원을 만드는 방법: 아무것도 안 쓰기
  for (const coin of coins) {      // 동전 루프가 바깥
    for (let a = coin; a <= amount; a++) {
      dp[a] += dp[a - coin];
    }
  }
  return dp[amount];
}

이 유형으로 풀어보기

거스름돈주어진 동전으로 금액을 만드는 데 필요한 최소 개수를 구해요.보통

← 배낭 문제