사용 개념: 동적 계획법.
이 방법을 떠올리는 신호는 “가짓수·최솟값·최댓값을 묻는데, 선택이 이어지고 같은 부분 상황이 여러 번 나오는” 문제다. 늘 같은 네 하위목표로 푼다.
- 상태 정하기: 표의 한 칸이 무엇을 뜻하는지 말로 적는다.
- 점화식 세우기: 그 칸의 답을 “마지막 선택”마다 나눠, 더 작은 칸으로 쓴다. 가짓수를 셀 때는 나눈 경우들이 빠짐없고 겹치지 않아야 더할 수 있다(합의 법칙). 최솟값·최댓값은 빠짐없기만 하면 경우가 겹쳐도 된다.
- 시작값 정하기: 더 쪼갤 수 없는 칸의 값을 정한다.
- 계산 순서 정하고 답 꺼내기: 점화식이 읽는 칸이 먼저 채워지도록 순서를 정하고, 답이 든 칸을 꺼낸다.
문제 1 · 완전한 풀이
계단을 한 번에 1칸 또는 2칸 오른다. 5칸을 오르는 방법은 몇 가지인가?
- 상태 정하기: dp[i] = i칸까지 오르는 방법의 수.
- 점화식 세우기: i칸에 도착하기 직전의 마지막 걸음은 1칸이거나 2칸이다. 1칸이면 그 전에 i − 1칸까지, 2칸이면 i − 2칸까지 올랐다. 두 경우는 겹치지 않으니 dp[i] = dp[i − 1] + dp[i − 2].
- 시작값 정하기: dp[0] = 1(아무것도 안 하는 한 가지), dp[1] = 1.
- 계산 순서 정하고 답 꺼내기: i = 2, 3, 4, 5 순서로 채운다. 답은 dp[5].
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| dp[i] | 1 | 1 | 2 | 3 | 5 | 8 |
dp 값 1, 1, 2, 3, 5, 8은 피보나치 수다. 칸이 많아지면 한 칸 늘 때마다 방법의 수가 약 1.618배가 되는데, 그 까닭은 선형 점화식에 있다.
dp = [1, 1] + [0] * (n - 1)
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
# n = 5 → 8
문제 2 · 마지막 하위목표를 채운다
격자 [[1, 3, 1], [1, 5, 1], [4, 2, 1]]의 왼쪽 위에서 오른쪽 아래까지 오른쪽이나 아래로만 간다. 지나는 칸(처음과 끝 포함)의 합을 가장 작게 하면?
- 상태 정하기: dp[r][c] = 왼쪽 위에서 (r, c)까지 오는 길의 최소 합.
- 점화식 세우기: (r, c)에는 위(r − 1, c)나 왼쪽(r, c − 1)에서 온다. dp[r][c] = min(dp[r − 1][c], dp[r][c − 1]) + 격자[r][c]. 맨 윗줄은 왼쪽에서만, 맨 왼쪽 줄은 위에서만 온다.
- 시작값 정하기: dp[0][0] = 격자[0][0] = 1.
- 계산 순서 정하고 답 꺼내기: __
답
위에서 아래로 줄마다, 줄 안에서는 왼쪽에서 오른쪽으로 채운다. 그러면 위 칸과 왼쪽 칸이 늘 먼저 채워져 있다. 답은 dp[2][2]다.
| 0열 | 1열 | 2열 | |
|---|---|---|---|
| 0행 | 1 | 4 | 5 |
| 1행 | 2 | 7 | 6 |
| 2행 | 6 | 8 | 7 |
답은 7이다(1 → 3 → 1 → 1 → 1).
최소 합 대신 길의 수를 세면, 같은 나누기에서 점화식이 “위에서 온 길 수 + 왼쪽에서 온 길 수”가 된다. 이것이 순열과 조합의 파스칼 항등식이고, (r, c)까지의 길은 \(\binom{r+c}{r}\)(\(\binom{\ }{\ }\)은 위의 수만큼 있는 것에서 아래의 수만큼 고르는 경우의 수)개다. 10 × 10 격자면 길이 48,620개지만, DP는 칸 100개만 채운다.
문제 3 · 하위목표 절반을 채운다
(무게, 값)이 (2, 3), (3, 4), (4, 5), (5, 6)인 물건 네 개가 있다. 물건은 하나씩만 있다. 무게 합 5 이하로 담아 값의 합을 가장 크게 하면?
- 상태 정하기: dp[w] = 지금까지 본 물건들로, 무게 합 w 이하로 담은 값의 최댓값.
- 점화식 세우기: __
- 시작값 정하기: 물건을 하나도 안 봤을 때 모든 w에서 dp[w] = 0.
- 계산 순서 정하고 답 꺼내기: __
답
-
물건 (무게 wt, 값 v)를 볼 때 마지막 선택은 “이 물건을 넣나, 안 넣나”다. 안 넣으면 dp[w] 그대로, 넣으면 dp[w − wt] + v다. dp[w] = max(dp[w], dp[w − wt] + v).
-
물건을 하나씩 보며, 물건마다 w를 큰 쪽에서 작은 쪽으로(5, 4, …, wt) 돌린다. 작은 쪽부터 돌리면 이미 이번 물건을 넣은 dp[w − wt]를 다시 읽어 같은 물건을 두 번 넣게 된다. 답은 dp[5]다.
답은 7이다. (2, 3)과 (3, 4)를 넣는다.
문제 4 · 혼자 풀기
수열 [10, 9, 2, 5, 3, 7, 101, 18]에서 앞에서 뒤로 순서를 지키며 몇 개를 골라, 고른 수가 점점 커지게 한다(가장 긴 증가하는 부분 수열). 가장 길게 몇 개를 고를 수 있는가?
답
dp[i]를 “i번째 수로 끝나는 가장 긴 증가 부분 수열의 길이”로 둔다. i번째 수 바로 앞에 고른 수를 j번째(j < i, a[j] < a[i])라 하면 dp[i] = max(dp[j] + 1)이고, 그런 j가 없으면 1이다. i를 앞에서부터 채우고, 답은 dp의 최댓값이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| a[i] | 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 |
| dp[i] | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 |
답은 4다. 예: 2, 5, 7, 101. 이 방법은 \(O(n^2)\)이다. 상태를 “i번째 수로 끝나는”으로 잡는 것이 핵심이다. “앞 i개 중 가장 긴 것”으로 잡으면 마지막 수를 몰라 다음 수를 이어 붙일 수 있는지 알 수 없다.