문제 보기 · Level 5 · 2021 카카오 채용연계형 인턴십 · 정답률 5% · 푼 사람 1,215명 (2026-09-30 기준)1
문제
시험장 n개가 이진 트리로 이어져 있고, 시험장마다 응시자 수가 있다. 간선 k − 1개를 끊어 시험장을 k개 그룹으로 나눈다. 인원이 가장 많은 그룹의 인원이 가장 작아지게 나눌 때, 그 인원을 돌려준다.
- 1 ≤ k ≤ n ≤ 10,000, 응시자 수 1 ~ 10,000
- links[i] = [i의 왼쪽 자식, 오른쪽 자식]이고, 자식이 없으면 −1이다
- 정확성(n ≤ 20)과 효율성을 따로 채점한다
풀이
막히면 한 단계씩 펼친다.
필요한 개념
매개변수 탐색: “가장 큰 그룹을 X명 이하로 하려면 몇 그룹이 필요한가?”로 질문을 바꾸고, 되는 X 중 가장 작은 것을 이분 탐색으로 찾는다. 필요한 그룹 수는 트리를 아래에서 위로 훑으며 센다. 그 순서는 깊이 우선 탐색으로 내려간 순서를 뒤집어 얻는다.
트리는 간선 하나를 끊을 때마다 한 덩어리가 정확히 둘로 갈라진다. 그래서 간선 j개를 끊으면 그룹은 j + 1개다.
1단계 · 작은 예로 손으로 풀기
문제의 예시 2~4의 트리다. 괄호 안이 응시자 수이고, 모두 27명이다.
3 (5명)
/ \
2 (7명) 1 (9명)
\
0 (6명)
- k = 1: 끊지 않는다. 27명이다.
- k = 2: 간선 하나를 끊는다. 3–2를 끊으면 {2, 0} 13명, {3, 1} 14명이라 14다. 3–1을 끊으면 18, 2–0을 끊으면 21이다. 답은 14다.
- k = 4: 간선을 다 끊는다. 가장 큰 시험장 하나인 9다.
2단계 · 가장 단순한 방법과 그 속도
끊을 간선 k − 1개를 모두 골라 보면 \(\binom{n-1}{k-1}\)가지다. 트리의 간선 n − 1개 가운데 k − 1개를 순서 없이 고르는 조합이다. n = 10,000, k = 5,000이면 이 수가 3,008자리다. 정확성 테스트(n ≤ 20)는 이렇게 통과해도, 효율성은 어림없다.
3단계 · 핵심 아이디어
- 질문 바꾸기: “가장 큰 그룹의 최솟값”을 바로 찾기는 어렵다. 대신 “모든 그룹을 X명 이하로 만들려면 최소 몇 그룹이 필요한가?”를 묻는다. 이 수가 k 이하면 X는 된다. 그룹이 k보다 적게 나와도, 간선을 더 끊으면 그룹은 늘고 그룹 인원은 줄기만 한다. X가 커지면 필요한 그룹 수는 줄거나 같다. 그래서 되는 X 중 가장 작은 것을 이분 탐색으로 찾는다. 범위는 가장 큰 시험장 인원부터 전체 인원까지다.
- X명 이하로 나누는 최소 그룹 수: 잎부터 올라가며 시험장마다 “자식 쪽에서 끊지 않고 올라온 인원”(up)을 본다.
- 나 + 왼쪽 up + 오른쪽 up ≤ X면 둘 다 붙인다.
- 아니고 나 + 작은 쪽 up ≤ X면, 큰 쪽 간선만 끊는다. 그룹이 1 는다.
- 그것도 안 되면 두 간선을 다 끊는다. 그룹이 2 는다.
- 왜 이 욕심이 맞나: 시험장마다 끊는 수를 먼저 줄이고, 끊는 수가 같으면 위로 올려 보내는 인원을 줄인다. 끊는 수를 하나 더 써서 위로 보내는 인원을 줄이는 방법은 이득이 없다. 그 한 번을 이 시험장과 부모 사이 간선에 쓰면, 끊는 수는 같고 위로 보내는 인원은 0이 되기 때문이다.
4단계 · 코드 흐름
- 아무의 자식도 아닌 번호가 뿌리다.
- 스택으로 뿌리부터 내려가는 순서를 만들고 뒤집는다. 그러면 자식이 부모보다 먼저 나온다.
- groups_needed(X): 그 순서대로 up을 채우며 끊은 수를 센다. 그룹 수는 끊은 수 + 1이다.
- lo = 가장 큰 시험장 인원, hi = 전체 인원으로 이분 탐색한다. groups_needed(mid) ≤ k면 hi = mid, 아니면 lo = mid + 1.
5단계 · 파이썬 코드
def children_first(links):
n = len(links)
is_child = [False] * n
for l, r in links:
if l != -1:
is_child[l] = True
if r != -1:
is_child[r] = True
order, stack = [], [is_child.index(False)] # 뿌리에서 시작
while stack:
v = stack.pop()
order.append(v)
for c in links[v]:
if c != -1:
stack.append(c)
return order[::-1] # 자식이 부모보다 먼저
def groups_needed(limit, num, links, order):
up = [0] * len(num)
cnt = 1
for v in order:
l, r = links[v]
a = up[l] if l != -1 else 0
b = up[r] if r != -1 else 0
if num[v] + a + b <= limit: # 둘 다 붙인다
up[v] = num[v] + a + b
elif num[v] + min(a, b) <= limit: # 큰 쪽을 끊는다
up[v] = num[v] + min(a, b)
cnt += 1
else: # 둘 다 끊는다
up[v] = num[v]
cnt += 2
return cnt
def solution(k, num, links):
order = children_first(links)
lo, hi = max(num), sum(num)
while lo < hi:
mid = (lo + hi) // 2
if groups_needed(mid, num, links, order) <= k:
hi = mid
else:
lo = mid + 1
return lo
- 재귀 대신 스택을 쓴다. 한 줄로 늘어진 트리는 깊이가 1만이라 파이썬 재귀 한도(기본 1,000)에 걸린다.
lo = max(num): X가 가장 큰 시험장보다 작으면 그 시험장 혼자서도 넘친다. 그래서 그보다 작은 X는 보지 않는다.up[l] if l != -1 else 0: 자식이 없으면 0명이 올라온다고 본다. 파이썬의up[-1]은 마지막 칸이라, 그냥 쓰면 엉뚱한 값을 읽는다.
6단계 · 실행 추적
1단계의 트리, k = 2다. 자식이 먼저인 순서는 0, 2, 1, 3이다.
| lo ~ hi | X | 3번에서 | 그룹 수 | 다음 범위 |
|---|---|---|---|---|
| 9 ~ 27 | 18 | 5 + 13 + 9 > 18, 5 + 9 ≤ 18이라 2쪽(13)을 끊는다 | 2 | 9 ~ 18 |
| 9 ~ 18 | 13 | 5 + 9 = 14 > 13이라 둘 다 끊는다 | 3 | 14 ~ 18 |
| 14 ~ 18 | 16 | 2쪽을 끊는다 | 2 | 14 ~ 16 |
| 14 ~ 16 | 15 | 2쪽을 끊는다 | 2 | 14 ~ 15 |
| 14 ~ 15 | 14 | 5 + 9 = 14라 2쪽을 끊는다 | 2 | 14 ~ 14 |
0번은 6, 2번은 7 + 6 = 13, 1번은 9가 늘 그대로 올라온다. 답은 14다.
7단계 · 복잡도와 흔한 실수
이분 탐색은 많아야 \(\lceil \log_2 10^8 \rceil\) = 27번쯤 돌고, 한 번에 시험장을 한 번씩 본다. 그래서 \(O(n \log S)\)다(S는 전체 인원). 시험장 1만 개(한 줄 트리, 무작위 트리)를 k 네 가지로 8번 풀어 0.3초쯤 걸렸다.
- 큰 쪽이 아니라 늘 왼쪽 간선을 끊는다. 작은 쪽을 남겨야 위로 올라가는 인원이 적다. 무작위 트리에서 틀리는 경우가 나왔다.
- 그룹 수를 “정확히 k”와 비교한다. k보다 적게 나와도 X는 된다. 이렇게 짜면 “된다/안 된다”가 X 순서대로 나뉘지 않아 이분 탐색이 틀린다. 무작위 트리에서 틀리는 경우가 나왔다. 이분법도 “함수가 끊기지 않는다”는 가정이 없으면 근이 아닌 곳으로 좁혀질 수 있다. 여기서는 “한 번 되면 계속 된다”가 그런 가정이라, 이것이 깨지면 반씩 줄여도 엉뚱한 X로 좁혀진다.
- 재귀로 짜서 한 줄 트리에서 재귀 한도에 걸린다.
-
프로그래머스 스쿨, “시험장 나누기” (https://school.programmers.co.kr/learn/courses/30/lessons/81305), 2026-10-01 조회. ↩