카카오 매출하락 최소화 - 트리 dp

처음 접해본 트리 dp 문제.. 

https://www.acmicpc.net/problem/2533

2533번: 사회망 서비스(SNS)

이 문제로 연습한번 하고 바로 들어갔다.

 

import sys
def solution(sales, links):
    def dfs(cur):
        check[cur] = False
        dp[cur][0] = 0  # 선택 안할경우
        dp[cur][1] = sales[cur-1]  # 선택 할경우
        for i in tree[cur]:
            if check[i]:
                dfs(i)
        if tree[cur]:
            for i in tree[cur]: ##### 선택 할경우
                dp[cur][1] += min(dp[i][0], dp[i][1])

            minimum = sys.maxsize
            for i in tree[cur]: #### 선택 안할경우
                cnt = dp[i][1]
                for j in tree[cur]:
                    if i != j:
                        cnt += min(dp[j][0], dp[j][1])
                minimum = cnt if cnt < minimum else minimum

            dp[cur][0] += minimum


    answer = 0
    personLen = len(sales)
    tree = [[] for _ in range(personLen + 1)]
    dp = [[0, 0] for _ in range(personLen + 1)]
    check = [True for _ in range(personLen + 1)]
    for Leader, sub in links:
        tree[Leader].append(sub)
    dfs(1)
    return min(dp[1][1], dp[1][0])

트리 dp 문제는 해당 노드를 선택할 경우와 선택안할 경우로 나누는데

##### 선택 할 경우의 dp[cur][1]에는 팀장을 선택했으니 하위 팀원들은 선택하거나 말거나 가장 작은 값을 더해준다.

#### 선택 안할경우의 dp[cur][0]은 각 자식노드를 순회하면서 첫번재 자식노드를 선택하면 나머지 자식노드는 선택하든 말든 작은 값들을 더해주고, 두번째 자식노드를 선택하면 나머지 자식노드는 선택하든 말든 작은값을 더해주고 를 반복해서 총합이 가장 작은 값을 뽑아내서 dp[cur][0]에다가 더해주면 된다.