[백준] 20364 부동산 다툼

문제

• 이진 트리 모양의 땅에서 루트 땅의 번호는 1이고, 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 × K, 오른쪽 자식 땅의 번호는 2 × K + 1이다.
• 오리들이 서있는 순서대로 원하는 땅을 가지도록 하는데, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅은 지날 수 없다.
• 각 오리별로 원하는 땅을 가질 수 있으면 0을, 가질 수 없다면 처음 마주치는 점유된 땅의 번호 출력하기
• 2 <= 땅 개수 N <= 2^20
  1 <= 오리 수 Q <= 200,000

 

풀이

• 땅 개수가 2^20 이므로 모든 땅을 리스트 형태로 저장할 수 없다.
• 이진 트리의 모양이므로 오리가 원하는 번호의 땅 번호에서부터 루트까지 거슬러 올라가면서 이미 점유된 땅이 있는지 확인한다.
  -> 트리에서 부모 = 자식 // 2 이기 때문에 역으로 확인한다.

 

import sys
input = sys.stdin.readline

N, Q  = map(int, input().split())
visited = set()         # 점유된 땅 번호
for _ in range(Q) :
    now = int(input())

    tax = set()         # 가는 길목에 있는 점유된 땅 번호
    x = now
    while x > 0 :
        if x in visited :
            tax.add(x)
        x //= 2
    
    visited.add(now)
    print(min(tax)) if tax else print(0)

 

References

• 백준 오늘의 문제