SWEA 5178 노드의 합 (python)

5178. [파이썬 S/W 문제해결 기본] 8일차 - 노드의 합 D3

문제

완전 이진 트리의 리프 노드에 1000이하의 자연수가 저장되어 있고, 리프 노드를 제외한 노드에는 자식 노드에 저장된 값의 합이 들어있다고 한다.

다음은 리프 노드에 저장된 1, 2, 3이 주어졌을 때, 나머지 노드에 자식 노드의 합을 저장한 예이다.

 

리프 노드 저장 값	자식 노드의 합을 저장한 상태

N개의 노드를 갖는 완전 이진 트리의 노드 번호는 루트가 1번이 되며, 같은 단계에서는 왼쪽에서 오른쪽으로 증가, 단계가 꽉 차면 다음단계의 왼쪽부터 시작된다.

완전 이진 트리의 특성상 1번부터 N번까지 빠지는 노드 번호는 없다.

리프 노드의 번호와 저장된 값이 주어지면 나머지 노드에 자식 노드 값의 합을 저장한 다음, 지정한 노드 번호에 저장된 값을 출력하는 프로그램을 작성 하시오.

**[입력]**

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

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

**[출력]**

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

 

 

풀이과정

 

왼쪽 오른쪽 나누어서 내려가면서 직접 검사하는 방법을 사용

 

푸는데

 

 if 2*n <=N :
        # 만약 값이 존재하지 않는다면 더 내려가보자
        if not tree[2*n]:
            # 한칸더 내려가기
            make_tree(2*n)
        # 왼쪽 값을 더해주자
        else: 
            tree[n] += tree[2*n]
    
    # 오른쪽 내려가기
    if 2*n+1 <= N:
        # 오른쪽 값이 없다면 내려가보자
        if not tree[2*n+1]:
            make_tree(2*n+1)
        # 있다면 더해주자
        else:
            tree[n] += tree[2*n+1]

else를 넣어서 풀었더니 값이 틀리게 나왔다.

정확히 어떻게 돌아가는지 순서는 자세히는 모르지만

그이유로는 아마 왼쪽 값이 더해져서 현재 노드에 값이 생길것이다.

그렇다면 현재 노드는 값이 있다고 추정되어 오른쪽 검사를 하거나 다른 검사를 할때 이것을 패스할 것이다.

 

풀이

import sys
sys.stdin = open("input.txt")

T = int(input())

def make_tree(n):


    # 맨밑까지 내려가 보자
    # 왼쪽 내려가는것
    # 왼쪽내려가는것이 범위 내에 있어야함
    if 2*n <=N :
        # 만약 값이 존재하지 않는다면 더 내려가보자
        if not tree[2*n]:
            # 한칸더 내려가기
            make_tree(2*n)
        # 왼쪽 값을 더해주자
        tree[n] += tree[2*n]
    
    # 오른쪽 내려가기
    if 2*n+1 <= N:
        # 오른쪽 값이 없다면 내려가보자
        if not tree[2*n+1]:
            make_tree(2*n+1)
        # 있다면 더해주자
        tree[n] += tree[2*n+1]







for tc in range(1, T+1):
    N, M, L = map(int, input().split())
    info = [list(map(int, input().split()))for _ in range(M)]

    tree = [0 for _ in range(N+1)]
    # 일단 주어진 값을 넣는다.
    for i in range(len(info)):
        tree[info[i][0]] = info[i][1]
    
    # 1부터 시작
    make_tree(1)
    # 원하는 노드 값 찾기
    result = tree[L]

    print("#{} {}".format(tc, result))

기타