백준 20364번 C++ 풀이

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

20364번: 부동산 다툼

시간 제한	메모리 제한	solved.ac 티어
2초	1024MB	실버 2

문제

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

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

---

문제와 그림에서 다 알려주듯이 이 문제는 이진트리에 관한 문제이긴 하지만, 굳이 이진트리를 사용할 필요 없이 단순히 배열로 풀 수 있는 문제이다.

 

처음에는 땅의 정보를 담은 land라는 class를 만들고, land 배열을 만들어서 처리했는데, 계속해서 오류가 나기도 했고, 굳이 어렵게 돌아가는 느낌이어서 다르게 풀었다.

 

땅이 차지되었는지 판단할 bool 배열을 세우고, 입력받은 땅으로부터 루트노드인 1번 땅까지 올라가면서 차지된 땅이 있는지 확인한다.

 

#include <bits/stdc++.h>
using namespace std;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q, num, temp;
    int ans = 0;
    cin >> n >> q;
    bool* land_tree = new bool[n + 1]; // true: 차지됨, false: 비어있음
    
    while(q--) {
        cin >> num;
        ans = 0;
        temp = num;
        while(temp) {
           if (land_tree[temp]) ans = temp;
           temp >>= 1;
        }
        if (!ans) land_tree[num] = true;
        cout << ans << '\n';
    }
}