문제 보기 · Level 4 · 2023 KAKAO BLIND RECRUITMENT · 정답률 8% · 푼 사람 998명 (2026-09-30 기준)1
문제
트리의 1번(뿌리)에 숫자 1, 2, 3 중 하나를 떨어뜨리면, 숫자는 “길”인 간선을 따라 리프까지 내려가 쌓인다. 처음에는 노드마다 번호가 가장 작은 자식이 길이다. 숫자가 지나간 노드는 길을 “다음으로 번호가 큰 자식”으로 바꾼다(가장 큰 자식 다음은 가장 작은 자식). 리프마다 쌓인 숫자의 합을 target과 같게 만드는 방법 중, 숫자를 가장 적게 쓰고 그중 사전 순으로 가장 앞선 떨어뜨리는 순서를 돌려준다. 불가능하면 [−1]이다.
- 간선 1 ~ 100개
- 리프의 target 0 ~ 100, 리프가 아닌 노드의 target은 0
풀이
막히면 한 단계씩 펼친다.
필요한 개념
1단계 · 작은 예로 손으로 풀기
뿌리 1에 리프 2, 3이 달려 있고 target은 2: 7, 3: 3이다.
- 떨어지는 리프는 2, 3, 2, 3, 2, …로 번갈아 정해진다. 숫자 값과 상관없다.
- 리프 2는 합 7을 만들려면 숫자가 적어도 3개(3 + 3 + 1) 필요하다. 리프 3은 합 3에 적어도 1개가 필요하다.
- 다섯 번 떨어뜨리면 2가 3번, 3이 2번 받는다. 2는 3개로 7(1 + 3 + 3), 3은 2개로 3(1 + 2)이 된다. 네 번이면 2가 2번뿐이라 7이 안 된다.
리프 2의 수 [1, 3, 3], 리프 3의 수 [1, 2]를 떨어지는 순서(2, 3, 2, 3, 2)대로 끼우면 [1, 1, 3, 2, 3]이다.
2단계 · 가장 단순한 방법과 그 속도
숫자 k개의 순서를 모두 해 보면 3ᵏ가지다. target 합이 수천이면 k도 수백 ~ 수천이라 어림없다.
3단계 · 핵심 아이디어
- 떨어지는 리프 순서는 정해져 있다: 길은 숫자 값과 상관없이 바뀐다. 그래서 i번째 숫자가 어느 리프에 떨어지는지 흉내 내어 미리 알 수 있다.
- 몇 개가 필요한가: 리프가 숫자를 c개 받으면 합은 c ~ 3c 사이의 무엇이든 만들 수 있다. 이것은 c에 대한 수학적 귀납법으로 보인다. c = 1이면 1 ~ 3이고, c개로 c ~ 3c를 모두 만들 수 있으면 하나를 더 받아 1, 2, 3을 더한 세 범위가 빈틈없이 이어져 c + 1 ~ 3c + 3을 모두 만든다. 그래서 모든 리프에서 c ≤ target ≤ 3c여야 한다.
- 가장 적은 수: 한 번에 하나씩 떨어뜨리며, 모든 리프가 3c ≥ target(모자라지 않음)이 되는 첫 순간에 멈춘다. 그 전에 어느 리프든 c > target(1씩 받아도 넘침)이 되면 그 뒤로도 늘 넘치니 [−1]이다. target이 0인 리프에 하나라도 떨어지면 바로 불가능이다.
- 사전 순으로 가장 앞서게: 리프마다 c개의 수를 앞자리부터 1, 2, 3 순으로 넣어 본다. 남은 자리 r개로 나머지 합을 채울 수 있으면(r ≤ 나머지 ≤ 3r) 그 수를 고른다. 리프끼리는 서로 영향이 없으니, 리프마다 가장 앞선 수열을 떨어지는 순서대로 끼우면 전체도 가장 앞선다.
4단계 · 코드 흐름
- 자식을 번호 순으로 정렬하고, 노드마다 지금 길인 자식의 순번 ptr을 0으로 둔다.
- 되풀이: 모든 리프가 3 × (받은 수) ≥ target이면 멈춘다. 아니면 뿌리부터 ptr을 따라 내려가며 ptr을 한 칸씩 돌리고, 도착한 리프의 받은 수를 1 늘려 순서에 적는다. 받은 수 > target이면 [−1].
- 리프마다 (받은 수, target)으로 가장 앞선 수열을 그리디로 만든다.
- 적어 둔 리프 순서대로 각 리프의 수열에서 하나씩 꺼내 답을 만든다.
5단계 · 파이썬 코드
def solution(edges, target):
n = len(target)
children = [[] for _ in range(n + 1)]
for p, c in edges:
children[p].append(c)
for ch in children:
ch.sort()
ptr = [0] * (n + 1)
leaves = [v for v in range(1, n + 1) if not children[v]]
need = {v: target[v - 1] for v in leaves}
cnt = {v: 0 for v in leaves}
order = []
def drop():
v = 1
while children[v]:
nxt = children[v][ptr[v]]
ptr[v] = (ptr[v] + 1) % len(children[v]) # 길을 다음 자식으로
v = nxt
return v
while not all(3 * cnt[v] >= need[v] for v in leaves):
leaf = drop()
cnt[leaf] += 1
order.append(leaf)
if cnt[leaf] > need[leaf]:
return [-1]
seqs = {}
for v in leaves:
c, t, s = cnt[v], need[v], []
for i in range(c):
rest = c - i - 1
for x in (1, 2, 3):
if rest <= t - x <= 3 * rest: # 남은 자리로 채울 수 있나
s.append(x)
t -= x
break
seqs[v] = s[::-1] # pop()으로 앞에서부터 꺼내려고 뒤집는다
return [seqs[leaf].pop() for leaf in order]
(ptr[v] + 1) % len(children[v]): 마지막 자식 다음은 0번째 자식으로 돌아간다.s[::-1]로 뒤집어 두면pop()이 맨 앞 수부터 준다. 리스트 맨 앞에서 빼는pop(0)보다 빠르다.
6단계 · 실행 추적
예시 1: 리프는 4, 7, 8, 9, 10이고 target은 4: 3, 7: 5, 8: 1, 9: 2, 10: 3이다.
| 떨어뜨린 차례 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 도착 리프 | 4 | 8 | 7 | 9 | 4 | 10 | 7 |
7번 뒤 받은 수는 4: 2, 7: 2, 8: 1, 9: 1, 10: 1이다. 모두 3 × 받은 수 ≥ target이라 멈춘다. 6번 뒤에는 7이 1개뿐이라(3 < 5) 모자랐다.
| 리프 | (받은 수, target) | 가장 앞선 수열 |
|---|---|---|
| 4 | (2, 3) | 1, 2 |
| 7 | (2, 5) | 2, 3 |
| 8, 9, 10 | (1, 1), (1, 2), (1, 3) | 1 / 2 / 3 |
도착 순서대로 끼우면 [1, 1, 2, 2, 2, 3, 3]이다.
7단계 · 복잡도와 흔한 실수
떨어뜨리는 횟수는 target 합(최대 약 1만) 이하이고, 한 번에 트리 깊이(≤ 100)만큼 내려간다. 멈춤 확인에 리프 수만큼 더 들어 약 수백만 번이면 끝난다.
- 숫자 값에 따라 떨어지는 곳이 바뀐다고 생각해 모든 경우를 해 본다.
- 가장 적은 개수를 정한 뒤에도 리프별 수열을 크게 고른다(3부터 채움). 사전 순으로 앞서려면 앞자리를 작게 둔다.
- target이 0인 리프에 숫자가 떨어지는 경우를 불가능으로 처리하지 않는다.
-
프로그래머스 스쿨, “1,2,3 떨어트리기” (https://school.programmers.co.kr/learn/courses/30/lessons/150364), 2026-09-30 조회. ↩