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

📖 문제

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

 

 

 

 

💡  풀이 방식

• 트리

필요 자료구조
- 점유된 땅의 수 저장하는 int형 배열
- 점유되었는지 상태를 표시할 boolean형 배열

 

 

1. 땅 개수 N과 오리 수 Q를 입력받는다.

2. i번째 오리가 원하는 땅 번호를 입력받는다.

3. 2에서 입력받은 오리가 원하는 땅 번호를 갈 수 있는지 확인해 출력한다.

  - 원하는 땅에서 1까지 거슬러 올라오며(/2) 점유된 상태인지 확인한다.

    ㄴ 점유된 상태인 경우, 점유된 땅의 번호를 정답으로 출력한다.

    ㄴ 정답이 초기값 0에서 바뀌지 않은 경우, 해당 번호의 땅을 점유 처리한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,Q;
    static int[] duck;
    static boolean[] chk;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());   // 땅 개수
        Q = Integer.parseInt(st.nextToken());   // 오리 수
        
        duck = new int[Q];
        for(int i = 0 ; i < Q ; i++) {
            duck[i] = Integer.parseInt(br.readLine());
        }
        
        chk = new boolean[N+1];
        for(int i = 0 ; i < Q ; i++) {
            solve(duck[i]);
        }
        System.out.println(sb.toString());
    }
    
    private static void solve(int num) {
        int idx = num;
        int ans = 0;
        
        // 원하는 땅에서 1까지 거슬러 올라오기
        while(idx != 0) {
            if(chk[idx]) { // 점유된 상태인 경우
                ans = idx;
            }
            idx /= 2; // 1칸 올라가기
        }
        
        sb.append(ans).append("\n");
        
        if(ans == 0)
            chk[num] = true;
  }
}

 

 

 

➕ 다른 풀이 방식

1칸 거슬러 올라갈 때 비트 연산을 사용하셨다. (>>1)

백준 20364 부동산 다툼 Java

---

💦 어려웠던 점

- 점유된 땅 상태를 언제 변경하지?의 문제..

 

 

🧐 새로 알게 된 내용

- 점유 처리 방법

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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