[백준] 20364번 : 부동산 다툼 (C++)

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

 

 

 

 

 

풀이)

 

// 20364. 부동산 다툼
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, q;
vector<int> vec;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> q;
    vec.resize(n + 1, 0);
 
    int a;
    for (int i = 0; i < q; i++)
    {
        // 주어지는 땅부터 
        // 역으로 거슬러 올라가는 방법을 사용했다.
        cin >> a;
        int t = a;
 
        // 점거하고 있는 마지막 땅을 체크
        int n_g = 0;
        bool flag = 0;
        while (t != 1)
        {
            // 이미 점유하고 있는 땅 중
            // 제일 마지막 땅을 찾는다.
            if (vec[t])
            {
                flag = 1;
                n_g = t;
            }
 
            t /= 2;
        }
 
        // 해당 땅을 점유하지 못함
        if (!flag)
        {
            vec[a] = 1;
            cout << "0\n";
        }
        // 역으로 돌아가봤을때 
        // 가장 마지막에 있는 점유된 땅
        else
        {
            cout << n_g << "\n";
        }
    }
 
    return 0;
}

---

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

20364번: 부동산 다툼