문제 보기 · Level 4 · 2021 KAKAO BLIND RECRUITMENT · 정답률 14% · 푼 사람 2,057명 (2026-09-30 기준)1

문제

직원 1번(CEO)을 뿌리로 한 나무 모양 조직도가 있다. 팀장과 그 바로 아래 팀원들이 한 팀이다(팀장은 다른 팀의 팀원일 수 있다). 모든 팀에서 적어도 한 명이 워크숍에 가야 한다. 가는 직원들의 하루 매출 합의 최솟값을 돌려준다.

  • 직원 2 ~ 300,000명, 매출 0 ~ 10,000
  • 답은 2³¹ − 1 이하

풀이

막히면 한 단계씩 펼친다.

필요한 개념

트리 DP: 직원마다 “이 사람이 갈 때”와 “안 갈 때”의 최소 비용을 두고, 팀원들의 값이 다 나온 뒤 팀장의 값을 만든다.

1단계 · 작은 예로 손으로 풀기

예시 4: 1 → 4 → 3 → 2 한 줄이고 매출은 1번 10, 2번 10, 3번 1, 4번 1이다. 팀은 (1, 4), (4, 3), (3, 2) 셋이다.

  • 3번과 4번을 보내면 1 + 1 = 2. 팀 (1, 4)는 4가, 팀 (4, 3)은 둘 다, 팀 (3, 2)는 3이 채운다.

답은 2다. 한 사람이 두 팀에 걸쳐 있으면(4번은 팀장이면서 팀원) 한 번 보내 두 팀을 채울 수 있다. 그래서 “누구를 보내나”가 이웃한 팀에 영향을 준다.

2단계 · 가장 단순한 방법과 그 속도

보낼 직원을 모두 고르면 2ⁿ가지다. 30만 명이면 어림없다.

3단계 · 핵심 아이디어

직원 v마다 v 아래 나무(v가 팀장인 팀과 그 아래 모든 팀)를 모두 채우는 최소 비용을 두 가지로 둔다.

  • go[v] = v가 간다: 매출[v] + (팀원 c마다 min(go[c], stay[c]))의 합. v가 가면 v의 팀은 이미 채워졌으니 팀원들은 자유롭다.
  • stay[v] = v가 안 간다:
    • v가 팀장이 아니면(팀원이 없으면) 0.
    • 팀원이 있으면 v의 팀을 팀원 누군가가 채워야 한다. 먼저 팀원마다 min(go[c], stay[c])를 더한다. 그중 누군가 go를 골랐다면(go[c] ≤ stay[c]) 이미 채워졌다. 아무도 go를 고르지 않았다면, 한 명을 억지로 보내야 하니 가장 적게 손해 보는 go[c] − stay[c]를 더한다.
  • 답: min(go[1], stay[1]).
4단계 · 코드 흐름
  1. links로 팀원 목록을 만든다.
  2. 1번에서 스택으로 내려가는 순서를 적는다.
  3. 그 순서를 거꾸로 돌며(팀원이 먼저) go, stay를 위 규칙으로 계산한다.
  4. min(go[1], stay[1])을 돌려준다.
5단계 · 파이썬 코드 
def solution(sales, links):
    n = len(sales)
    children = [[] for _ in range(n + 1)]
    for a, b in links:
        children[a].append(b)
    order, stack = [], [1]
    while stack:                               # 뿌리부터 내려가는 순서
        v = stack.pop()
        order.append(v)
        stack.extend(children[v])
    go = [0] * (n + 1)                         # v가 간다
    stay = [0] * (n + 1)                       # v가 안 간다
    for v in reversed(order):                  # 팀원이 먼저
        base = sum(min(go[c], stay[c]) for c in children[v])
        go[v] = sales[v - 1] + base
        if not children[v]:
            stay[v] = 0
        elif any(go[c] <= stay[c] for c in children[v]):
            stay[v] = base
        else:
            stay[v] = base + min(go[c] - stay[c] for c in children[v])
    return min(go[1], stay[1])
  • 재귀로 짜면 조직도가 한 줄로 30만 명일 때 RecursionError가 난다. 순서를 미리 적고 거꾸로 돈다.
  • sales[v - 1]: 직원 번호는 1부터, 리스트는 0부터다.
6단계 · 실행 추적

예시 1: 1번 아래 9, 5, 3번 / 9번 아래 7번 / 5번 아래 4, 10번 / 10번 아래 8, 6, 2번

직원 (매출) go stay 까닭
2, 3, 4, 6, 7, 8(팀원만) 자기 매출 0  
10 (17) 17 0 + min(16, 14, 17) = 14 팀원 8, 6, 2 중 누군가 가야 한다
5 (19) 19 + 0 + 14 = 33 0 + 14 + min(18, 17 − 14) = 17 10번을 보내는 손해가 3으로 가장 적다
9 (28) 28 0 + 13 = 13 7번을 보낸다
1 (14) 14 + 13 + 17 + 0 = 44 30 + min(28 − 13, 33 − 17, 15) = 45  

답은 min(44, 45) = 44다. 1번, 7번, 10번을 보낸다.

7단계 · 복잡도와 흔한 실수

직원마다 팀원 수만큼 보니 \(O(n)\)이다. 30만 명이 한 줄로 이어진 조직도에서 재 보니 0.2초가 안 걸렸다.

  • stay[v]에서 “팀원 중 한 명은 가야 한다”를 빼먹어 v의 팀을 비워 둔다.
  • 팀원마다 억지로 보내는 손해를 모두 더한다. 한 명만 가면 되니 가장 작은 손해 하나만 더한다.
  • 팀원이 없는 직원에게도 “누군가 가야 한다”를 적용한다. 팀원이 없으면 그가 팀장인 팀이 없다.
검증: 문제의 예시 4개를 통과했고, 6단계 표의 go, stay 값을 코드로 확인했다. 무작위 조직도 1,500개(직원 10명 이하)에서 “보낼 직원을 모두 골라 모든 팀이 채워졌는지 보는” 풀이와 결과가 같았다. 30만 명의 시간도 쟀다 — 32_pg72416_p1.py

  1. 프로그래머스 스쿨, “매출 하락 최소화” (https://school.programmers.co.kr/learn/courses/30/lessons/72416), 2026-09-30 조회. ↩