📚 단일 패턴

322. Coin Change

Bottom-up 동적 계획법으로 목표 금액을 만들기 위한 최소 동전 개수를 계산하기

Oct 3, 2025 — dynamic-programming

문제 설명

LeetCode 322. Coin Change (opens in a new window)

풀이 아이디어

이런 문제는 어떻게 풀어야 할까 ?
- 특별한 방법 보다는 전체 다 해봐야할 것 같다. => 동적계획법 적용해보자.
Dynamic Programming 프레임
- 선택 : i번째 동전을 사용하는 경우, 사용하지 않는 경우
- 상태 : dp[i]는 i번째 동전까지 고려했을때, 최소 동전 갯수

해결 전략

dp[i]는 i번째 동전까지 고려했을때, 최소 동전 갯수
- 최종 최소값을 찾아야 하므로 default 값은 최소값에서 가장 먼 값인 Infinity 로 초기화
- dp[0] = 0 은 0 원을 만드는 경우는 0 개의 동전이 필요하므로 0 으로 초기화

    const dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;

가장 중요한 부분

    // bottom up 으로 순회 [1, ..., amount] (상태)
    for (let i = 1; i <= amount; i += 1) {
      // coin 은 상태는 아니지만 경우의 수를 체크하기 위해서 순회
        for (const coin of coins) {
            if (i - coin < 0) continue;  // 기준 값보다 잔돈 금액이 더 큰 경우, 동전 교환 할 수 없음.

            dp[i] = Math.min(
                dp[i],           // 이전 i번째 동전까지 고려했을때의 최소 동전 갯수 (어떤 coin 을 사용했는지 상관없이 최소값)
                1 + dp[i-coin]   // i 번째 이번 coin 동전을 사용하는 경우
                                 // : 1 개의 coin 동전 (가치는 coin) 을 사용하고 가격 (i-coin) 동전까지 고려했을때의 최소 동전 갯수
            )
        }
    }

구현

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    const dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i += 1) {
        for (const coin of coins) {
            if (i - coin < 0) continue;

            dp[i] = Math.min(
                dp[i],
                1 + dp[i-coin]
            )
        }
    }

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