LeetCode 322 Coin Change 풀이: 최소 동전 수를 구하는 동적 계획법

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

• 문제: 322. Coin Change
• 출처: LeetCode
• 자체 판단 난이도: Level 3

각 동전을 무제한으로 사용할 수 있을 때 목표 금액을 만드는 최소 동전 수를 구한다. 금액별 최솟값을 갱신하는 동적 계획법이 필요하고, 그리디가 항상 통하지 않는 이유도 살펴봐야 하므로 Level 3으로 판단했다.

1. 문제 요약

동전 종류를 담은 배열 coins와 목표 금액 amount가 주어진다. 각 동전을 무제한으로 사용해 목표 금액을 만들 때 필요한 최소 동전 개수를 반환한다. 만들 수 없으면 -1을 반환한다.

예를 들어 coins = [1, 2, 5], amount = 11이면 5 + 5 + 1로 3개의 동전을 사용할 수 있다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

점화식 도출

dp[x]를 금액 x를 만드는 데 필요한 최소 동전 수라고 정의한다. 마지막에 사용한 동전이 coin이라면 그 동전을 사용하기 전에는 x - coin을 만들어 둔 상태다.

dp[x] = min(dp[x - coin] + 1)  (coin <= x)

금액 0은 동전을 사용하지 않는 방법 하나로 만들 수 있으므로 dp[0] = 0이다. 나머지 금액은 아직 만들 수 없는 상태로 초기화하고 작은 금액부터 채운다.

상태 전이는 amount = 6, coins = [1, 3, 4]에서 다음처럼 진행된다. 각 금액에서 마지막으로 사용할 동전을 하나씩 가정하고, 이미 계산한 나머지 금액의 최소 동전 수에 1을 더해 비교한다.

6에서는 마지막 동전을 3으로 두면 dp[6 - 3] + 1 = 2가 된다. 4를 마지막 동전으로 두는 경우는 dp[2] + 1 = 3이므로, 둘 중 작은 2를 선택한다.

그리디가 아닌 동적 계획법을 사용하는 이유

동전 액면가가 임의로 주어지면 큰 동전부터 고르는 선택이 최적해를 보장하지 않는다. 각 금액에서 가능한 마지막 동전을 모두 비교하고, 그중 동전 수가 가장 적은 결과를 선택해야 한다.

amount + 1은 만들 수 없는 금액을 표시한다

동전 값은 모두 양수이므로 금액 x를 만들 때 필요한 동전 수는 많아야 x개다. 따라서 amount + 1은 어떤 유효한 답보다도 큰 센티넬 값으로 쓸 수 있다. dp[x - coin]이 아직 도달 불가능한 상태라면 여기에 1을 더해도 센티넬보다 작아지지 않으므로 min 갱신에 선택되지 않는다. 마지막에 dp[amount]가 여전히 센티넬인지 확인하면 만들 수 없는 경우를 -1로 구분한다.

금액을 작은 값부터 계산하는 순서도 무제한 재사용을 가능하게 한다. 현재 금액보다 작은 x - coin의 최솟값은 이미 계산되어 있으므로 같은 액면가를 여러 번 이어 붙일 수 있다.

3. 문제 해결 코드 (Python)

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        impossible = amount + 1
        dp = [impossible] * (amount + 1)
        dp[0] = 0

        for current in range(1, amount + 1):
            for coin in coins:
                if coin <= current:
                    dp[current] = min(
                        dp[current],
                        dp[current - coin] + 1,
                    )

        return -1 if dp[amount] == impossible else dp[amount]

금액 amount 각각에 대해 동전 종류를 확인하므로 시간 복잡도는 O(amount × k)다. 여기서 k는 동전 종류의 개수다. DP 배열을 하나 사용하므로 공간 복잡도는 O(amount)다.

4. 오답 접근과 반례

가장 큰 동전부터 사용하는 그리디 접근은 모든 동전 체계에서 최적이 아니다. 예를 들어 coins = [1, 3, 4], amount = 6에서 가장 큰 동전 4를 먼저 고르면 남은 금액은 2이고 결과는 4 + 1 + 1, 즉 3개다. 하지만 3 + 3은 2개이므로 그리디 결과가 최솟값이 아니다.

또 다른 실수는 도달할 수 없는 금액을 0으로 남겨두는 것이다. coins = [2]에서 금액 3은 만들 수 없으므로 0개가 아니라 -1이어야 한다. 이 때문에 도달 불가능한 상태는 별도의 큰 초기값으로 구분한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 만들 수 있는 금액과 불가능한 금액을 확인할 수 있다.

solver = Solution()
assert solver.coinChange([1, 2, 5], 11) == 3
assert solver.coinChange([2], 3) == -1
assert solver.coinChange([1], 0) == 0
assert solver.coinChange([1, 3, 4], 6) == 2

5. 공식 예제와 추가 검증

LeetCode 공식 예제 3개를 Python 3.12.4에서 실행했고 기대값과 일치했다.

추가 검증 1: 정확히 동전 하나로 만드는 경우

입력: coins = [2, 5], amount = 10
기대 출력: 2
확인 결과: 통과
검증 목적: 같은 동전을 여러 번 사용할 수 있는지 확인

추가 검증 2: 홀수 금액을 만들 수 없는 경우

입력: coins = [2, 4], amount = 7
기대 출력: -1
확인 결과: 통과
검증 목적: 도달 불가능한 상태를 -1로 반환하는지 확인

추가 검증 3: 최대 금액 경계

입력: coins = [1], amount = 10000
기대 출력: 10000
확인 결과: 통과
검증 목적: 제한 금액에서도 DP 배열과 반복 계산이 정상 동작하는지 확인

6. 참고 풀이 비교

• Coin Change 공식 문제는 동전의 무제한 사용과 최소 동전 수, 불가능한 경우의 반환값을 정의한다.
• AlgoMonster의 설명은 금액별 최소값을 이전 금액의 결과에서 만드는 동적 계획법 전이를 설명한다.

재귀에 메모이제이션을 적용하는 방식도 같은 상태를 저장하므로 O(amount × k) 시간과 O(amount) 공간으로 해결할 수 있다. 이 글에서는 작은 금액부터 결과를 채우는 상향식 방식을 사용해 재귀 호출과 호출 스택을 제거했다.

마무리

Coin Change는 동전의 액면가에 따라 그리디가 실패할 수 있다는 점과, 작은 금액의 최적해를 재사용하는 동적 계획법을 함께 보여주는 문제다. dp[0] = 0에서 시작해 각 금액에 마지막으로 사용할 동전을 시도하면 최소 동전 수와 불가능한 금액을 모두 일관되게 처리할 수 있다.