회사 조직도에서 팀장이 팀원들의 보고를 다 받은 뒤 자기 보고서를 쓰듯, 자식들의 답이 다 나오면 그것으로 부모의 답을 만든다. 잎에서 시작해 뿌리까지 올라가며 칸마다 한 번씩만 계산한다. 보통 “이 칸을 골랐을 때”와 “안 골랐을 때”처럼 칸마다 답을 두세 개 들고 다닌다. 나무가 한 줄로 길면 재귀가 깊어져 파이썬 재귀 한도에 걸리니, 순서를 미리 구해 반복문으로 돈다.
예시로 보기
아래 나무에서 서로 이웃하지 않게(부모와 자식을 함께 고르지 않게) 칸을 골라 값의 합을 가장 크게 한다. 괄호 안이 값이다.
1(5)
/ \
2(3) 3(4)
/ \ \
4(6) 5(2) 6(1)
칸마다 두 값을 둔다. 안 고름 = v를 고르지 않을 때 v 아래 나무의 최대 합, 고름 = v를 고를 때의 최대 합.
| 칸 | 안 고름 | 고름 | 까닭 |
|---|---|---|---|
| 4, 5, 6(잎) | 0 | 6, 2, 1 | 자기 값뿐 |
| 2 | max(0, 6) + max(0, 2) = 8 | 3 + 0 + 0 = 3 | 2를 고르면 4, 5는 못 고른다 |
| 3 | max(0, 1) = 1 | 4 + 0 = 4 | |
| 1 | max(8, 3) + max(1, 4) = 12 | 5 + 8 + 1 = 14 |
답은 max(12, 14) = 14다. 1, 4, 5, 6을 고른다.
정의
뿌리 있는 나무에서 칸 v의 자식들을 \(C(v)\), 값을 \(w(v)\)라 하자.
\[\text{안}(v) = \sum_{c \in C(v)} \max(\text{안}(c), \text{고}(c)), \qquad \text{고}(v) = w(v) + \sum_{c \in C(v)} \text{안}(c).\]안(v)는 v를 고르지 않을 때, 고(v)는 v를 고를 때 v 아래 나무에서 얻는 가장 큰 합이다. v를 고르면 이웃인 자식은 고를 수 없어서 고(v)에는 자식의 안(c)만 더한다. v를 고르지 않으면 자식마다 더 큰 쪽을 고른다.
잎이면 안(v) = 0, 고(v) = w(v)다. 답은 max(안(뿌리), 고(뿌리))다.
v를 고르지 않으면 자식마다 고르든 말든 자유라 더 큰 쪽을 더한다. v를 고르면 자식은 모두 고를 수 없다. 자식들의 나무는 서로 겹치지 않아 따로 가장 좋게 고르면 된다1.
계산 순서: 자식이 부모보다 먼저 계산되어야 한다. 뿌리에서 DFS나 BFS로 방문 순서를 적은 뒤, 그 순서를 거꾸로 돌면 늘 자식이 먼저다. 후위 순회와 같은 효과다.
order, stack = [], [root]
while stack: # 뿌리부터 내려가는 순서
v = stack.pop()
order.append(v)
stack.extend(children[v])
for v in reversed(order): # 거꾸로: 자식이 먼저
skip = sum(max(dp[c]) for c in children[v])
take = value[v] + sum(dp[c][0] for c in children[v])
dp[v] = (skip, take)
활용
- 비용: 칸마다 자식 수만큼 본다. 자식 수를 모두 더하면 간선 수이고, 칸이 n개인 나무의 간선은 n − 1개다(트리의 동치 조건 5). 그래서 전체 \(O(n)\)이다.
- 알아보는 신호: 나무(조직도, 폴더, 부모-자식) 위에서 최대·최소를 구하는데, 한 칸의 선택이 이웃(부모·자식)에만 영향을 준다.
- 쓰는 곳: 회사 파티 초대(상사와 부하를 함께 부르지 않기), 나무 위의 감시 카메라 배치, 폴더 크기 합, 나무의 지름.
- 흔한 실수: 재귀로 짜서 깊은 나무에서
RecursionError가 난다. “고름”에 자식의 max를 더해 부모·자식을 함께 고른다. 부모에서 자식으로만 간선을 만들지 않고 양방향으로 넣은 뒤 부모를 자식으로 또 센다.
연결
- 선수: 동적 계획법, 깊이 우선 탐색(DFS), 트리 순회와 이진 탐색 트리
- 트리 DP는 나무의 재귀적 정의(뿌리 하나와 서로 겹치지 않는 자식 나무들)를 따라 값을 정한다. 재귀적 정의와 구조적 귀납법의 잎 세기 \(\text{leaves}(T) = \text{leaves}(T_L) + \text{leaves}(T_R)\)가 칸마다 값을 하나만 들고 다니는 가장 단순한 트리 DP다. 표가 맞다는 것도 구조적 귀납법으로 증명한다. 잎에서 맞고, 자식 나무들에서 맞으면 부모에서도 맞는다.
- 층마다 번갈아 고르는 그리디식 방법은 틀린다(확인 문제 C3). 나무는 이분 그래프라서 짝수 층과 홀수 층이 두 색으로 나뉜다. 그래서 이 방법은 이웃끼리 함께 고르지는 않지만, 합이 가장 큰 답을 놓칠 수 있다.
- 연습: 매출 하락 최소화
확인 문제
C1 예시 나무에서 칸 4의 값을 6에서 1로 바꾸면 칸 2와 칸 1의 (안 고름, 고름)과 답은?
답: 칸 2는 (max(0, 1) + max(0, 2), 3) = (3, 3). 칸 3은 (1, 4) 그대로. 칸 1은 (max(3, 3) + max(1, 4), 5 + 3 + 1) = (7, 9). 답은 9다(1, 4, 5, 6 → 5 + 1 + 2 + 1 = 9).
C2 “안 고름(v)”에서 자식마다 max(안, 고)를 더하는데, “고름(v)”에서는 안(c)만 더하는 까닭은?
답: v를 고르면 자식 c는 v와 이웃이라 고를 수 없으니 c의 “안 고름” 값만 쓸 수 있다. v를 고르지 않으면 c를 고르든 말든 규칙에 어긋나지 않으니, 둘 중 큰 쪽을 쓴다.
C3 “짝수 층 칸을 모두 고르는 것과 홀수 층 칸을 모두 고르는 것 중 큰 쪽”이 틀리는 나무를 들어라.
답: 한 줄로 이어진 칸 10 – 1 – 1 – 10. 짝수 층(첫째, 셋째)은 11, 홀수 층(둘째, 넷째)도 11이다. 양 끝 10과 10을 고르면 20이고 서로 이웃하지 않는다. 한 층을 통째로 고르지 않아도 되기 때문이다.
-
칸마다 “고름/안 고름” 두 값을 두는 나무 위 DP는 Cormen 외, Introduction to Algorithms 3판, 15장 끝 문제 15-6 “Planning a company party”(상사와 부하를 함께 초대하지 않는 파티)와 같은 구조다[확인필요: 문제 번호는 판에 따라 다를 수 있다]. ↩