[Python] 백준 13325번: 이진 트리

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

13325번: 이진 트리

1. 현재노드를 기준으로 최장길이를 구한다. 현재노드 > 다음노드 길이 + 다음노드 최장길이

2. 최장길이를 기준으로 양쪽노드에서 길이가 작은 노드의 길이를 올려준다. ( 현재노드 > 다음노드 길이 = 

현재노드의 최장길이 - 다음노드의 최장길이가 된다.

노드를 루트1부터 왼쪽부터 시작하면 3번 노드를 기준으로하면 최장길이는 3이된다. 3에서6번노드의 길이가 더 짧으므로 현재노드의 최장길이(3) - 6번노드의 최장길이(0) 즉 3번노드에서 6번노드로가는 길이는 6으로 갱신된다.

 

import sys
from collections import deque
input = sys.stdin.readline

n = int(input().strip())
a = deque(list(map(int, input().split())))
tree = {i: {} for i in range(1, 2 ** (n+1))}
dp = [[0, 0] for _ in range(2**(n+1))]  # 최장길이, 합
for i in range(1, 2 ** n):
    tree[i][i*2] = a.popleft()
    tree[i][i*2+1] = a.popleft()

def dfs(x, s):
    if x == n-1:
        maxx = max(tree[s][s*2], tree[s][s*2+1])
        dp[s] = [maxx, 2 * maxx]
        return [maxx, 2*maxx]
    else:
        dp[s][0] = max(tree[s][s*2] + dfs(x+1, s*2)[0],
                       tree[s][s*2+1] + dfs(x+1, s*2+1)[0])
        dp[s][1] = dp[s*2][1] + dp[s*2+1][1] + \
            dp[s][0] - dp[s*2][0] + dp[s][0] - dp[s*2+1][0]
        return dp[s]

print(dfs(0, 1)[1])