[BOJ/Silver 1] 백준 20364 부동산 다툼(C++)

문제 링크

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

 

문제

이진 트리 모양의 땅으로 이루어진 꽉꽉마을에는 오리들이 살고 있다. 땅 번호는 다음과 같이 매겨진다.

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을, 갈 수 없다면 처음 마주치는 점유된 땅의 번호를 출력한다.

 

예제 입력 1

6 4
3
5
6
2

예제 출력 1

0
0
3
0

 

 

알고리즘 분류

• 자료 구조

 

풀이

이진 트리의 특성을 이용하여 주어진 X를 1이 될 때까지 2로 나누며 값에 해당하는 땅이 이미 점유되었는지 파악하고, 점유된 땅 중 가장 낮은 번호를 출력한다.

마지막으로 오리가 해당 땅을 점유했음을 기록한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, Q, X;
bool DP[2 << 20];

void input() {
    cin >> N >> Q;
    while (Q--) {
        cin >> X;
        int Answer = 0;
        int TmpX = X;
        while (TmpX > 1) {
            if (DP[TmpX]) {
                Answer = TmpX;
            }
            int NextX = TmpX / 2;
            TmpX = NextX;
        };
        DP[X] = true;
        cout << Answer << "\n";
    };
}

int main() {
    FASTIO
    input();

    return 0;
}