2021 카카오 코딩테스트 lv.4 매출 하락 최소화 파이썬

def solution(sales, links):
    sales = [0] + sales
    tree = [[] for _ in range(len(sales)+1)]
    for a,b in links:
        tree[a].append(b)
    d = [[0,0] for _ in range(len(sales)+1)]
    dfs(1,d,tree,sales)
    return min(d[1])

def dfs(node,d,tree,sales):

    if not tree[node]:
        d[node][0] = sales[node]
        d[node][1] = 0
        return

    d[node][0] = sales[node]
    min_gap = float('inf')

    for i in tree[node]:
        dfs(i, d, tree, sales)
        d[node][0] += min(d[i])
        min_gap = min(min_gap,d[i][0]-d[i][1])
        if min_gap < 0:
            min_gap = 0

    d[node][1] = d[node][0] + min_gap - sales[node]

 

트리 dp 문제입니다.

 

tree[node][0] = node번 직원이 워크숍에 참석했을 경우

tree[node][1] = node번 직원이 워크숍에 참석하지 않았을 경우

 

만약 A라는 팀에 

1 = 팀장 

2,3,4 = 팀원 일때,

 

tree[1][0] 일때 1은 무조건 워크숍에 참석하고, 나머지 2,3,4는 워크숍에 참석할수도, 참석 안할수도 있습니다.

만약 2,3,4밑에 팀원들이 더 있어 새로운 팀이 존재한다면, 1이 워크숍에 참석했을 때 2,3,4도 워크숍에 참석할수도 있습니다. 이 경우 tree[1][0]은 하위 트리의 값들까지 모두 가지고 있습니다.

tree[1][1] 일때 1은 워크숍에 참석하지 않기때문에, 나머지 2,3,4 중 최소 한명은 워크숍에 참석해야 합니다.

 

 

코드에서 min_gap은 모든 팀이 워크샵에 참석해야 하는 조건을 만족시키기 위해 필요한 값입니다.

만약 min_gap이 0보다 작다면 조건을 만족하므로 값을 0으로 바꿔줍니다.