[Python/파이썬] 백준 13116번: 30번

문제

 

풀이

완전 이진트리 및 LCA 문제이다.

완전 이진트리의 레벨은 log₂를 통해 구할 수 있고 부모는 /2를 해주면 된다.

 

즉 두 노드의 레벨을 구한 뒤, 레벨을 서로 같게 맞춰준 뒤, 두 노드가 서로 같을 때까지 각 노드에 /2를 해주면 된다.

(이진트리와 LCA를 공부하면 쉽게 풀 수 있다.)

 

코드

import sys, math
input = sys.stdin.readline

t = int(input())

def getLevel(n):
    return math.floor(math.log2(n))

for _ in range(t):
    a, b = map(int, input().split())
    while True:
        levelA, levelB = getLevel(a), getLevel(b)
        if levelA > levelB:
            a //= 2
        elif levelA < levelB:
            b //= 2
        else:
            break
    while a != b:
        a //= 2
        b //= 2
    print(a * 10)

 

마무리

트리 문제가 이런 식으로도 활용되는구나 싶은 문제였다.