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

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

 

 

이 문제는 이진트리 모양으로 땅이 구성되며 오리들이 차지하려는 땅이 주어질때 각 오리들이 땅을 차지하는 경우, 못차지하는 경우를

출력하는 문제이다.

 

이진트리 모양이기 때문에 하나의 노드는 최대 2개의 자식노드를 가질 수 있으며 그 자식노드들의 부모노드에 접근하기 위해서는

자식 노드 / 2를 하면 부모노드에 접근할 수 있다.

 

그렇다면 오리들이 차지하려는 땅에서 루트 노드(1)까지 올라가며 차지된땅인지만 확인하면 된다고 생각하였다.

만약 차지된 땅이면 갈 수 없는 땅이기 때문에 앞에 차지된 땅을 출력하였고 1까지 갔을때

차지된 땅을 만나지 않았으면 갈 수 있다고 생각하여 0을 출력하였다.

따라서 시간복잡도는 계속 2로 나누기 때문에 O(Q log N)이다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N, Q;
bool tree[1100000];

void solve() {

}

void input() {
    cin >> N >> Q;

    for(int i = 0; i < Q; i++) {
        int a;
        cin >> a;
        int tmp = a;
        int res = 0;
        bool flag = false;
        while(tmp != 1) {
            if(tree[tmp]) {			// 1까지 올라갈때 차지된 땅을 만나는 경우
                flag = true;
                res = tmp;
            }
            tmp /= 2;
        }
        if(flag) {
            cout << res << endl;
        }
        else {
            tree[a] = true;
            cout << 0 << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}