[대회][BOJ][INU 코드페스티벌 2020] D번 20364 : 부동산 다툼

문제를 정리해보자.

 

 

 

<트리 구조>

1. 루트 땅의 번호는 1이다.

2. 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 x k, 오른쪽 자식 땅의 번호는 2 x (k + 1)이다.

 

 

트리 구조

 

 

<문제>

1. 오리들은 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 있다.

2. 오리들이 서 있는 순서대로 원하는 땅을 가지도록 한다.

3. 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 지나가지 못한다.

이 경우 처음 마주치는 점유된 땅의 번호를 출력한다. (지나가는 길에는 오리가 원하는 땅도 포함이다.)

4. 오리가 원하는 땅까지 간다면 0을 출력한다.

 

 

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

 

 

오리의 번호가 아래 식으로 루트 노드까지 간다.

 

 

 

 

 

import sys

input = sys.stdin.readline

N, Q = map(int, input().split())  # 땅의 수, 오리 수

dp = [0] * (N + 1)

for _ in range(Q):
    q = int(input())
    cal = q
    tmp = -1

    while 0 < cal:  # 루트 노드까지
        if dp[cal] == 1:  # 소유지 확인
            tmp = cal

        if cal % 2 == 0:  # 짝수
            cal = cal // 2

        else:
            cal = (cal-1) // 2  # 홀수
    dp[q] = 1

    if tmp > 0:
        print(tmp)
    else:
        print(0)

 

 

소유지 중에 루트 노드와 가까운 노드를 출력한다.

소유지가 없었다면, 0을 출력한다.

 

 

근데 이 문제 왜 시간 초과가 안 나는지 모르겠다.

노드의 수는 N, 오리의 수는 Q이다.

모든 오리가 루트 노드까지 가는 시간 복잡도는  O(N x Q)이다.

 

노드의 수는 최대 2^20이고, 오리의 수는 최대 200,000이다.

그러면 최대 209,715,200,000이다. 제한 시간인 2초를 훨씬 넘는다.

근데 왜 시간제한에 걸리지 않을까? 아직 모르겠다.