DP 상태·점화식·계산 순서

큰 동전부터 고르면 항상 최소가 아니라는 반례를 보았습니다. 목표는 모든 유효한 마지막 동전 선택을 비교해 최소를 구하는 동적 계획법을 설계하는 것입니다. 함수·목록·최솟값과 탐욕 반례를 복습하세요.

개념과 약속

동적 계획법(DP)은 겹치는 부분 문제의 답을 보존해 다시 계산하지 않는 방법입니다. '작은 문제를 풀고 합친다'는 말만으로는 부족합니다. 상태가 무엇을 뜻하는지, 선택을 비교하는 점화식, 작은 상태부터 계산하는 순서를 정해야 합니다. 여기 상태 best[x]는 금액 x를 만드는 최소 동전 개수입니다. best[0]=0, 아직 만들 수 없으면 무한대입니다.

마지막 동전 c를 떼면 금액 x-c의 최적 답에 하나를 더합니다. 가능한 c들의 best[x-c]+1 중 최소를 택합니다. 모든 동전은 양의 정수이므로 참조 상태가 더 작습니다. previous[x]에는 선택한 마지막 동전을 저장해 개수만이 아니라 실제 구성을 복원합니다. 같은 개수의 여러 답은 입력 동전 순서에 따라 하나를 반환합니다.

손으로 상태 추적하기

동전 [4,3,1], 금액 6입니다.

6의 후보는 마지막 4이면 best[2]+1=3, 3이면 best[3]+1=2, 1이면 best[5]+1=3입니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

import math

def minimum_coins(amount, coins):
    if amount < 0 or any(coin <= 0 for coin in coins):
        raise ValueError("nonnegative amount and positive coins required")
    best = [0] + [math.inf] * amount
    previous = [None] * (amount + 1)
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value and best[value - coin] + 1 < best[value]:
                best[value] = best[value - coin] + 1
                previous[value] = coin
    if best[amount] == math.inf:
        return None
    result = []
    while amount:
        coin = previous[amount]
        result.append(coin)
        amount -= coin
    return result


print(minimum_coins(6, [4, 3, 1]))
print(minimum_coins(3, [2]))
print(minimum_coins(0, [4, 3, 1]))

실행 결과:

[3, 3]
None
[]

왜 맞고 언제 끝나는가

어떤 구성도 마지막 동전 하나와 남은 금액으로 나눌 수 있습니다. 남은 부분이 최적이 아니면 더 좋은 부분으로 바꾸어 전체를 개선할 수 있으므로 최적 답은 점화식의 후보 중 하나입니다. 작은 금액의 최적값이 먼저 계산되어 각 단계가 맞습니다. 계산 범위는 유한하고 복원 때 금액이 양의 동전만큼 줄어 끝납니다.

비용과 적용 범위

금액 A, 동전 종류 C개면 O(AC) 시간, 표·복원 기록 O(A) 공간입니다. 입력 금액의 비트 수는 log A이므로 금액 자체에 비례한 이 비용은 숫자가 매우 큰 문제에서 무겁습니다. 이런 분석을 의사다항 시간이라고 부르기도 합니다. 실제 반환 동전 수만큼 복원 비용도 있습니다.

스스로 풀어 보기

1. 동전 [5,4,1]로 금액 8을 만드는 최소 구성과 탐욕 구성을 비교하세요.
2. 동전 0을 허용하면 계산·복원 순서의 어떤 근거가 사라지나요?

힌트

1. best[4]를 이용합니다.
2. 금액이 엄격히 줄어야 합니다.

해설

1. 최소는 4+4 두 개, 탐욕은 5+1+1+1 네 개입니다.
2. x-0이 같은 상태라 작은 상태부터 계산하는 전제가 깨지고 복원도 금액을 줄이지 못할 수 있습니다. 양의 동전 제약을 시작 전에 검사합니다.

흔한 오해

DP는 표를 만드는 것 자체가 아닙니다. 상태 의미와 모든 최적 선택을 포괄하는 점화식이 먼저입니다.

복습과 다음 연결

피보나치는 중복 계산을 없애는 저장 방식 둘을, LCS는 두 방향 상태를 다룹니다.