SWEA 5178 노드의 합

문제출처 SW Expert Academy
문제의 저작권은 SW Expert Academy에 있습니다.

문제소개

5178 노드의합 
- 노드갯수 N, 리프노드갯수 M, 출력노드번호 L 
- 리프(최하단)노드의 번호와 그 노드의 값이 주어진다. 
- 부모노드는 자식노드의 저장된 값의 합이 들어간다. 
- 위와 같은 규칙으로 완전이진트리를 만든다고 할 때, 
- 지정한 번호의 노드 값을 출력하는 프로그램을 작성 

입력:
1
5 3 2 (노드 5개, 리프노드 3개, 출력노드 2)
4 1 (4번 노드 값은 1)
5 2 (5번 노드 값은 2)
3 3 (3번 노드 값은 3)

출력:
#1 3 (2번 노드의 값은 3, 자식노드의 값 1 + 2, 자식노드 = 4번, 5번노드)  

풀이접근

1. 노드의 개수(N)만큼 완전이진트리를 만듦
2. 입력받은 리프노드 값을 트리에 대입
2. 부모노드(i//2)에 자식노드의 값을 더함 

코드

for tc in range(int(input())):
    # 노드 N개, 리프노드 M개, 출력노드 L번
    N, M, L = map(int, input().split()) 
    tree = [0 for _ in range(N+1)] # 루트노드 번호가 1이니 +1
   
    for _ in range(M): # 리프노드번호와 값 입력받고 트리에 대입
        idx, value = map(int, input().split()) 
        tree[idx] = value
        
    for i in range(N, 0, -1): 
        # 마지막 노드부터 역순으로 부모노드 값 대입
        if i // 2 > 0:
            tree[i//2] += tree[i]
            
    print(f'#{tc+1} {tree[L]}')

 1
 5 3 2
 4 1
 5 2
 3 3


#1 3

정의된 변수 값 확인

tree

[0, 6, 3, 3, 1, 2]

i # i는 N부터 역순으로 1까지

1