노드의 합 Python(SW Expert Academy)

난이도 : D2

문제번호 : 5178

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

완전 이진 트리의 리프 노드에 1000이하의 자연수가 저장되어 있고, 리프 노드를 제외한 노드에는 자식 노드에 저장된 값의 합이 들어있다고 한다. 다음은 리프 노드에 저장된 1, 2, 3이 주어졌을 때, 나머지 노드에 자식 노드의 합을 저장한 예이다. N개의 노드를 갖는 완전 이진 트리의 노드 번호는 루트가 1번이 되며, 같은 단계에서는 왼쪽에서 오른쪽으로 증가, 단계가 꽉 차면 다음단계의 왼쪽부터 시작된다. 완전 이진 트리의 특성상 1번부터 N번까지 빠지는 노드 번호는 없다. 리프 노드의 번호와 저장된 값이 주어지면 나머지 노드에 자식 노드 값의 합을 저장한 다음, 지정한 노드 번호에 저장된 값을 출력하는 프로그램을 작성 하시오.

 

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50 다음 줄부터 테스트 케이스의 별로 노드의 개수 N과 리프 노드의 개수 M, 값을 출력할 노드 번호 L이 주어지고, 다음 줄부터 M개의 줄에 걸쳐 리프 노드 번호와 1000이하의 자연수가 주어진다.

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 5 3 2 4 1 5 2 3 3 10 5 2 8 42 9 468 10 335 6 501 7 170 17 9 4 16 479 17 359 9 963 10 465 11 706 12 146 13 282 14 828 15 962	#1 3 #2 845 #3 1801

---

2. 문제풀이

Pull Binary Tree 이므로 배열로 풀어도 된다. 노드의 개수만큼 배열을 생성한 뒤, 원하는 노드의 값이 없다면 왼쪽자식과 오른쪽 자식위 위치를 구해 피보나치 수열마냥 dp를 이용하여 값을 구한다.

---

3. 소스코드

#D2 5178 노드의 합
def dfs(idx):
    #만약 인덱스 범위를 벗어난다면 0을 리턴
    if idx > N + 1: return 0
    #값이 있다면 값을 리턴
    if Tree[idx]: return Tree[idx]
    #왼쪽 자식노드 위치찾기
    left = idx*2
    #오른쪽 자식노드 위치찾기
    right = left+1
    #재귀를 이용하여 구하기
    Tree[idx] = dfs(left) + dfs(right)
    #결과값 리턴
    return Tree[idx]
 
 
for t in range(int(input())):
    #별도 노드개수, 리프노드의 개수, 출력노드번호
    N, M, L = map(int, input().split())
    #누적합을 적어둔 리스트
    Tree = [0 for _ in range(N+2)]
    #입력값을 받아 노드의 값을 수정한다.
    for i in range(M):
        node, value = map(int, input().split())
        Tree[node] = value
    #재귀를 이용하여 계산시작
    result = dfs(L)
    #결과값 출력
    print('#{} {}'.format(t+1, result))