[프로그래머스] 매출 하락 최소화

문제 요약

회사 조직은 CEO를 루트로 하는 트리다. 각 팀은 팀장과 그의 직속 팀원들로 이루어진다.

워크숍에 참석하는 직원들의 매출액 합을 최소화해야 하며, 모든 팀에서 팀장 또는 팀원 중 적어도 한 명은 반드시 참석해야 한다.

핵심 아이디어

각 직원에 대해 두 가지 상태를 계산한다.

• dp[node][0]: 현재 직원이 워크숍에 참석하지 않을 때 서브트리의 최소 매출 손실
• dp[node][1]: 현재 직원이 워크숍에 참석할 때 서브트리의 최소 매출 손실

직원 node의 직속 팀원을 child라고 하자.

현재 직원이 참석하는 경우

현재 팀에는 이미 참석자가 있으므로, 각 팀원은 참석/불참 중 비용이 작은 쪽을 자유롭게 선택하면 된다.

dp[node][1]
= sales[node]
+ sum(min(dp[child][0], dp[child][1]))

현재 직원이 참석하지 않는 경우

팀장인 현재 직원이 불참하므로, 직속 팀원 중 적어도 한 명이 참석해야 한다.

먼저 모든 팀원의 더 작은 비용을 더한다.

base = sum(min(dp[child][0], dp[child][1]))

이 선택만으로 참석한 팀원이 없다면, 한 명을 참석 상태로 바꿔야 한다. 이때 비용 증가가 가장 작은 팀원을 선택한다.

extra = min(dp[child][1] - min(dp[child][0], dp[child][1]))
dp[node][0] = base + extra

팀원이 없는 말단 직원은 자신의 팀을 구성하지 않으므로, 불참 비용은 0이다.

풀이 과정

1. links로 각 직원의 직속 팀원 목록을 만든다.
2. CEO(0번 인덱스)부터 반복 DFS를 수행하여 방문 순서를 만든다.
3. 방문 순서를 역순으로 처리하면, 모든 팀원의 DP가 먼저 계산되는 후위 순회가 된다.
4. 각 직원의 참석/불참 DP를 계산한다.
5. CEO의 참석과 불참 중 최솟값을 반환한다.

Python 코드

def solution(sales, links):
    employee_count = len(sales)
    children = [[] for _ in range(employee_count)]

    # 직원 번호는 1부터 시작하므로 인덱스로 사용하기 위해 1을 뺀다.
    for leader, member in links:
        children[leader - 1].append(member - 1)

    # 재귀 깊이 제한을 피하기 위해 반복 DFS로 순서를 만든다.
    order = []
    stack = [0]

    while stack:
        node = stack.pop()
        order.append(node)

        for child in children[node]:
            stack.append(child)

    # dp[node][0]: node가 불참할 때의 최소 비용
    # dp[node][1]: node가 참석할 때의 최소 비용
    dp = [[0, 0] for _ in range(employee_count)]

    # 자식부터 처리하도록 방문 순서를 뒤집는다.
    for node in reversed(order):
        attend_cost = sales[node]
        absent_cost = 0
        extra_cost = float("inf")

        for child in children[node]:
            child_absent = dp[child][0]
            child_attend = dp[child][1]
            child_minimum = min(child_absent, child_attend)

            # 현재 직원이 참석한 경우, 자식은 더 저렴한 상태를 선택한다.
            attend_cost += child_minimum

            # 현재 직원이 불참한 경우의 기본 비용
            absent_cost += child_minimum

            # 자식을 참석 상태로 고정할 때 필요한 최소 추가 비용
            extra_cost = min(extra_cost, child_attend - child_minimum)

        dp[node][1] = attend_cost

        if not children[node]:
            # 말단 직원은 자신의 팀 조건을 만족시킬 필요가 없다.
            dp[node][0] = 0
        else:
            # 팀장이 불참하면 직속 팀원 중 한 명 이상은 참석해야 한다.
            dp[node][0] = absent_cost + extra_cost

    return min(dp[0][0], dp[0][1])

코드 설명

extra_cost는 “기본 선택에서 참석자가 없을 수도 있는 상황”을 해결하는 값이다.

예를 들어 직속 팀원들의 최소 선택이 모두 불참이라면, 팀장도 불참할 때 팀 전체가 불참하게 된다. 이때 팀원 한 명을 참석으로 바꿔야 하며, 그중 비용 증가량이 가장 작은 값을 더한다.

반대로 어떤 팀원의 참석 비용과 불참 비용이 같다면:

child_attend - child_minimum  # 0

이 팀원을 참석으로 바꿔도 비용이 늘지 않으므로, 팀 참석 조건을 추가 비용 없이 만족할 수 있다.

시간 복잡도

N을 직원 수라고 하자.

• 트리 생성: O(N)
• 반복 DFS: O(N)
• DP 계산: O(N)

각 직원과 연결은 한 번씩만 확인한다.

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

정리

이 문제의 포인트는 팀장 불참 상태에서 “직속 팀원 중 최소 한 명 참석” 조건을 놓치지 않는 것이다. 자식들의 최소 비용을 먼저 더하고, 필요할 때만 가장 적은 추가 비용으로 한 명을 참석 처리하면 전체 최솟값을 구할 수 있다.