[백준 20364번] 파이썬 - 부동산 다툼

백준 20364 - 부동산 다툼

시간 제한 2초, 메모리 제한 1024MB

# 조건

• 이진 트리 모양의 땅으로 이루어진 꽉꽉마을에는 오리들이 살고 있다. 땅 번호는 다음과 같이 매겨진다.
  1. 루트 땅의 번호는 1이다.
  2. 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 × K, 오른쪽 자식 땅의 번호는 2 × K + 1이다.
• 어느날 오리들끼리 부동산 다툼이 일어나서 꽉꽉마을 촌장 경완이가 해결책을 가져왔고, 그 내용은 다음과 같다.
  1. 오리들을 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 위치해 있다.
  2. 오리들이 서있는 순서대로 원하는 땅을 가지도록 한다.

• 만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을 지나가지 못해 그 오리는 땅을 가지지 못한다.
• 오리가 원하는 땅까지 가는 길에는 오리가 원하는 땅도 포함된다.
• 경완이의 해결책대로 땅 분배를 했을 때 각 오리별로 원하는 땅을 가질 수 있는지, 가질 수 없다면 처음 마주치는 점유된 땅의 번호를 구해보자.

입력

• 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N < 220, 1 ≤ Q ≤ 200,000)
• 두 번째 줄부터 차례로 Q개의 줄에 걸쳐 i+1번째 줄에는 i번째 오리가 원하는 땅 번호 xi_가 주어진다. (2 ≤ _xi ≤ N)

출력

• Q개의 줄에 원하는 땅에 갈 수 있다면 0을, 갈 수 없다면 처음 마주치는 점유된 땅의 번호를 출력한다.

# 접근 방법

• 전형적인 트리 문제이다.
• 우선 점유된 땅을 표시할 tree 리스트를 N+1개의 크기만큼 만들어준다.
• 이후 오리들이 원하는 땅을 입력받고 check 함수를 수행해준다.
  • 인자로는 현재 탐색할 땅 번호와 기존에 점유된 땅을 지났는지의 여부이다.
  • 현재 땅 (idx) = 1이라면 루트 땅까지 왔으므로 flag를 리턴해준다.
  • 그렇지 않다면 3가지 조건으로 나눈다.
    • 현재 점유된 땅을 지나지 않았고 지금 땅도 비어있는 경우
    • 현재 땅이 점유되어 있는 경우
    • 점유된 땅을 지나서 온 경우
  • 현재 땅이 점유되어 있는 경우를 우선적으로 조건문을 넣어준 이유는 가장 깊은 곳에서 출발하기 때문에 맨 처음 만나는 땅으로 flag를 변경시켜주기 위해서이다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def check(idx, flag):  
    if idx == 1:  
        return flag  
    if not flag and not tree[idx]:  
        result = check(idx//2, flag)  
    elif tree[idx]:  
        result = check(idx//2, idx)  
    elif flag:  
        result = check(idx//2, flag)  

    return result  

N, Q = map(int, input().split())  
tree = [False] * (N+1)  
for _ in range(Q):  
    num = int(input())  
    val = check(num, 0)  
    if not val:  
        print(0)  
        tree[num] = True  
    else:  
        print(val)