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

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

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

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

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

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]에다가 더해주면 된다.

from http://mvmvm.tistory.com/145 by ccl(A) rewrite - 2021-09-10 15:26:57