[SWEA] 5178. 노드의 합

문제

풀이

• 현재 노드에 저장된 값이 없다면 자식 노드들로부터 값을 가져와서 합한 값을 저장한다 => 재귀함수로 구현
• 처음 실행될 때는 값이 리프 노드에만 있기 때문에 리프노드까지 내려가게되고 리프 노드에는 값이 존재하기 때문에 바로 값만 리턴

def leaf(n):
    if n <= N:
        if not tree[n]:
            tree[n] = leaf(2*n) + leaf(2*n+1)
        return tree[n]
    return 0

T = int(input())
for tc in range(1, T+1):
    N, M, L = map(int, input().split())
    tree = [0] * (N+1)
    for _ in range(M):
        idx, v = map(int, input().split())
        tree[idx] = v

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

풀이2(다른사람..)

• 리프 노드에 값을 입력
• 리프 노드부터 거꾸로 올라가면서 부모 노드에 값을 저장 (자식노드번호//2 = 부모노드번호)

T = int(input())
for tc in range(1, T+1):
    N, M, L = map(int, input().split())
    tree = [0] * (N+1)
    for _ in range(M):
        leaf, num = map(int, input().split())
        tree[leaf] = num            
    for i in range(N, 1, -1):       
        tree[i//2] += tree[i]       

    print(f'#{tc} {tree[L]}')