[BOJ] 백준 20364번: 부동산 다툼

문제 설명

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

1. 루트 땅의 번호는 1이다.
2. 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 × K, 오른쪽 자식 땅의 번호는 2 × K + 1이다.

어느날 오리들끼리 부동산 다툼이 일어나서 꽉꽉마을 촌장 경완이가 해결책을 가져왔고, 그 내용은 다음과 같다.

1. 오리들을 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 위치해 있다.
2. 오리들이 서있는 순서대로 원하는 땅을 가지도록 한다.

만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을 지나가지 못해 그 오리는 땅을 가지지 못한다. 오리가 원하는 땅까지 가는 길에는 오리가 원하는 땅도 포함된다.

경완이의 해결책대로 땅 분배를 했을 때 각 오리별로 원하는 땅을 가질 수 있는지, 가질 수 없다면 처음 마주치는 점유된 땅의 번호를 구해보자.

 

문제 풀이

이 문제는 트리에 대한 개념을 물어보는 문제입니다. 1부터 원하는 땅까지 간다는 내용이 적혀있는데 반대로 원하는 땅에서 1까지 거슬러 올라오면서 소유자가 있는지 없는지 체크하면 더 쉽게 해결할 수 있습니다.

 

풀이 코드

Java

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, Q;
    static boolean[] map;
    static int[] duck;

    static void input() throws IOException{
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        map = new boolean[N+1];
        duck = new int[Q];
        for(int i=0; i<Q; i++)
            duck[i] = Integer.parseInt(br.readLine());
    }

    static void process(){
        for(int i=0; i<Q; i++)
            findRoute(duck[i]);
        System.out.print(sb);
    }

    private static void findRoute(int num) {
        int idx = num;
        int ans = 0;
        while(idx != 0){
            if(map[idx])
                ans = idx;
            idx /=2;
        }
        sb.append(ans).append('\n');
        if(ans == 0) map[num] = true;
    }

    public static void main(String[] args) throws IOException{
        input();
        process();
    }
}

 

C++

#include<iostream>
using namespace std;

int findRoute(bool* map, int num) {
    int idx = num;
    int ans = 0;
    while (idx != 0) {
        if (map[idx]) {
            ans = idx;
        }
        idx /= 2;
    }
    if (ans == 0) map[num] = true;
    return ans;
}

int main() {
    int N, Q;
    cin >> N >> Q;

    bool *map = new bool[N + 1];
    int* duck = new int[Q];
    for (int i = 0; i < N + 1; i++) map[i] = false;
    for (int i = 0; i < Q; i++) {
        int num;
        cin >> num;

        duck[i] = findRoute(map, num);
    }
    for (int i = 0; i < Q; i++) cout << duck[i] << endl;
}

 

<출처>

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

20364번: 부동산 다툼