동작 원리

대부분의 DP 풀이는 같은 다섯 가지 질문으로 설계합니다. 이 장에서는 이 질문들을 최소 동전 교환과 최장 공통 부분 수열(LCS)이라는 두 고전 문제에 적용하고, 표를 손으로 채워 가며 답이 만들어지는 과정을 따라갑니다.

다섯 단계 설계법

1. 상태: 부분 문제를 가리키는 매개변수는 무엇인가? 답을 결정하는 데 필요한 가장 작은 집합을 고릅니다.
2. 점화식: 작은 상태들로 이 상태의 답을 어떻게 계산하는가? 보통 "가능한 선택을 모두 해 보고 가장 좋은 것을 남긴다"는 형태입니다.
3. 기저 사례: 바로 답할 수 있는 상태는 무엇인가?
4. 순서: 의존하는 값이 먼저 준비되려면 어떤 순서로 계산해야 하는가? (메모이제이션은 이 순서를 자동으로 찾습니다.)
5. 최종 답: 어느 상태에 답이 들어 있고, 선택 내용까지 복원해야 하는가?

예제 1: 최소 동전 교환

동전 단위가 [1, 3, 4]이고 각 동전을 몇 개든 쓸 수 있을 때, 정확히 6을 만드는 최소 동전 개수는 얼마일까요?

큰 동전부터 고르는 그리디는 4, 1, 1로 동전 세 개를 씁니다. 하지만 3 + 3이면 두 개로 충분합니다. 그리디가 틀리므로 DP를 씁니다.

• 상태: dp[a] = 금액 a를 만드는 최소 동전 수
• 점화식: c <= a인 모든 동전 c에 대해 dp[a] = 1 + min(dp[a - c])
• 기저 사례: dp[0] = 0. 만들 수 없는 금액은 무한대로 둡니다.
• 순서: a가 커지는 순서. dp[a]는 더 작은 금액에만 의존합니다.
• 최종 답: dp[6]

왼쪽부터 표를 채우면 다음과 같습니다.

답은 dp[6] = 2입니다. "마지막 동전" 열을 거꾸로 따라가면 실제 동전도 알 수 있습니다. 6에서 3을 쓰고 3으로, 다시 3을 쓰고 0으로 갑니다.

import math


def min_coins(coins: list[int], amount: int) -> tuple[int, list[int]]:
    dp = [0] + [math.inf] * amount
    last = [0] * (amount + 1)
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                last[a] = c
    if dp[amount] == math.inf:
        return -1, []
    used, a = [], amount
    while a > 0:
        used.append(last[a])
        a -= last[a]
    return dp[amount], used


print(min_coins([1, 3, 4], 6))  # (2, [3, 3])
print(min_coins([5, 10], 3))    # (-1, [])

같은 점화식을 하향식으로 쓰면 정의와 거의 똑같이 읽힙니다. 캐시 덕분에 각 금액은 한 번만 계산됩니다.

import math
from functools import cache


def min_coins(coins: tuple[int, ...], amount: int) -> int:
    @cache
    def best(a: int) -> float:
        if a == 0:
            return 0
        return min((1 + best(a - c) for c in coins if c <= a), default=math.inf)

    result = best(amount)
    return -1 if result == math.inf else int(result)


print(min_coins((1, 3, 4), 6))  # 2

예제 2: 최장 공통 부분 수열

부분 수열은 문자의 순서는 지키되 중간 문자를 건너뛸 수 있는 문자열입니다. a = "ABCBA"와 b = "BCAB"에 모두 들어 있는 가장 긴 부분 수열은 무엇일까요?

• 상태: L[i][j] = a의 앞 i글자와 b의 앞 j글자의 LCS 길이
• 점화식: a[i-1] == b[j-1]이면 L[i][j] = L[i-1][j-1] + 1, 아니면 L[i][j] = max(L[i-1][j], L[i][j-1])
• 기저 사례: L[0][j] = L[i][0] = 0 (빈 접두사와는 공통 문자가 없습니다)
• 순서: 위 행부터, 각 행은 왼쪽부터. 각 칸은 위, 왼쪽, 왼쪽 위 대각선 칸이 필요합니다.
• 최종 답: L[5][4]

오른쪽 아래 칸이 LCS 길이 3을 알려 줍니다. 실제 수열은 그 칸에서 거꾸로 걸어가며 찾습니다. 두 문자가 같으면 그 문자를 고르고 대각선으로, 다르면 값이 큰 이웃 쪽으로 이동합니다. 값이 같은 이웃이 있으면 "BCB"나 "BCA"처럼 길이는 같지만 다른 답이 나올 수 있습니다.

def lcs_table(a: str, b: str) -> list[list[int]]:
    L = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    return L


for row in lcs_table("ABCBA", "BCAB"):
    print(row)
# 마지막으로 출력되는 행: [0, 1, 2, 3, 3]

정리

• DP는 상태, 점화식, 기저 사례, 순서, 최종 답의 다섯 질문으로 설계합니다.
• 작은 표를 손으로 채워 보는 것이 점화식을 검증하는 가장 빠른 방법입니다.
• 값뿐 아니라 실제 해가 필요하면 상태마다 고른 선택을 저장하거나 표를 거꾸로 따라갑니다.