백준 20364 부동산 다툼 Java

백준 20364 부동산 다툼 Java

728x90

solved.ac = 실버 2

https://www.acmicpc.net/problem/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('

'); } System.out.println(sb.toString()); }

3. 전체 코드

728x90

from http://dhbang.tistory.com/32 by ccl(A) rewrite - 2021-12-16 16:01:33