[백준 9934번] 완전 이진 트리 (Silver1)

https://www.acmicpc.net/problem/9934

9934번: 완전 이진 트리

import sys

k=int(sys.stdin.readline())
array=list(map(int,sys.stdin.readline().split()))

layer=[[] for _ in range(k+1)]
for n in range(k,0,-1):
    i=0
    while 2**(k-n)+i*(2**(k-n+1))<2**k:
        layer[n].append(array[2**(k-n)+i*(2**(k-n+1))-1])
        i+=1

for i in range(1,k+1):
    for value in layer[i]:
        print(value,end=' ')
    print()

 

layer마다 원소 사이 간격이 일정한 것을 찾을 수 있었다.

 

k= 트리 높이

n= layer 층 수

i= layer 층 내의 i번째 원소(인덱스 0이 첫번째 원소)

 

트리 높이가 k인 n번째 layer에서 i번째 원소의 순서 = 2**(k-n)+i*(2**(k-n+1))

즉, 높이가 5인 5번째 layer에서 1번째 원소의 순서 = 2**(5-5)+0*(2**(5-5+1)) = 1