백준 20364 부동산 다툼 Java

solved.ac = 실버 2

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

20364번: 부동산 다툼

 

1. 접근

 

 

땅의 개수가 1,048,576개, 오리의 수가 200,000 마리로 모두 최대치로 주어졌을 때 인접 리스트를 생성하고 각 마리마다 모든 땅을 살펴본다면 시간 초과가 발생할 수 있는 문제이다.

 

처음에는 단순히 루트 -> 오리가 원하는 땅으로 접근을 했으나 강사님의 스켈레톤 코드에서 오리의 땅 -> 루트로 가는 방법이 더 간단히 찾을 수 있다는것에 힌트를 얻어 접근해 보았다.

 

그래프를 생성하지 않고 각 오리의 원하는 땅에서부터 시작해 루트까지 가려면 현재 노드의 부모를 찾아가는 방법을 찾아야 했는데 힌트는 문제에 있었다!

문제의 예제 트리를 이진법으로 변환하여 접근한다면

현재 노드에서 오른쪽으로 한 칸 시프트 하면 부모의 노드가 된다.

100(4) -> 10(2) -> 1

101(5) -> 10(2) -> 1

110(6) -> 11(3) -> 1

 

입력받은 오리가 원하는 땅에서부터 한 칸씩 시프트하며 루트를 향해 가고 boolean 배열에 저장해두자!

 

2. 풀이

 

변수 세팅

static int N, Q;
static int[] ducks;
static boolean[] visit;
public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken()); // 땅의 개수
    Q = Integer.parseInt(st.nextToken()); // 오리의 마리 수
    ducks = new int[Q];
    for (int i = 0; i < Q; i++) ducks[i] = Integer.parseInt(br.readLine());
    solution();
}

 

탐색

static void solution() {
    visit = new boolean[N + 1];
    for (int x : ducks) {
        int answer = 0, tmp = x;
        // 오리가 원하는 땅에서부터 루트를 향해 찾아가자!
        while (x != 1) {
            // 경로에 이미 땅의 소유주가 있다!
            if (visit[x]) answer = x;
            // 한 칸 올라가자!
            x >>= 1;
        }
        visit[tmp] = true;
        // 소유주가 있는 땅을 만났으면 해당 땅의 번호일거고
        // 만나지 않았다면 초기값인 0으로 있다!
        sb.append(answer).append('\n');
    }
    System.out.println(sb.toString());
}

 

3. 전체 코드