SWEA 5178 노드의 합 (파이썬)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

---

아이디어

1. 이 문제는 완전이진트리로 주어지는 것 같다.
2. 후위 순회하며 값을 구하면 되겠다.

 

---

풀이

def postorder(v):
    if v <= N:
        postorder(v*2)
        postorder(v*2+1)
        if tree[v] == 0:
            tree[v] = tree[v*2] + tree[v*2+1]

for tc in range(int(input())):
    N, M, L = map(int, input().split())
    tree = [0] * 1000
    for m in range(M):
        e, n = map(int, input().split())
        tree[e] = n

    postorder(1)
    print(f'#{tc+1}', tree[L])

 

---

후기 및 해설

• 예상대로 후위 순회하며 가지고 있는 값이 0인 노드에 대해 왼쪽, 오른쪽 자식들을 더해서 구하면 되었다.
• 그런데, 트리를 줄 범위를 처음에 100으로 줬었는데, 1000으로 줬어야 했다.
• 문제를 잘 읽고 나올 수 있는 수의 범위를 고려해야겠다.