[백준]#11812 K진 트리

문제

각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다.

트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다.

아래 그림은 노드 9개로 이루어져 있는 3진 트리이다.

노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다.

다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y ≤ N, x ≠ y)

출력

총 Q개의 줄을 출력한다. 각 줄에는 입력으로 주어진 두 노드 사이의 거리를 출력한다.

예제 입력 1

7 2 3
1 2
2 1
4 7

예제 출력 1

1
1
4

예제 입력 2

9 3 3
8 9
5 7
8 4

예제 출력 2

2
2
3

풀이

이 문제는 최고 공통 조상 알고리즘을 이용해서 풀 수 있었다. 이 문제의 경우 K가 1일 때 특수 상황이기 때문에 따로 처리해야했던 부분이 생각하기 어려웠다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static long N;
    static int K;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Long.parseLong(input[0]);
        K = Integer.parseInt(input[1]);
        int Q = Integer.parseInt(input[2]);
        StringBuilder sb = new StringBuilder();

        if(K==1) {
            for(int i=0; i<Q; i++) {
                input = br.readLine().split(" ");

                sb.append(Math.abs(Long.parseLong(input[0]) - Long.parseLong(input[1]))).append("\n");
            }
        }

        else {
            for(int i=0; i<Q; i++) {
                input = br.readLine().split(" ");

                long ans = lca(Long.parseLong(input[0]), Long.parseLong(input[1]));
                sb.append(ans).append("\n");
            }
        }

        System.out.print(sb.toString());
    }

    public static long lca(long a, long b) {
        long distance = 0;

        while(true) {
            if(a==b)
                return distance;

            long depth_a = cal_depth(a);
            long depth_b = cal_depth(b);

            if(depth_a==depth_b) {
                while(a!=b) {
                    a = (a-2)/K + 1;
                    b = (b-2)/K + 1;
                    distance += 2;
                }
            }

            else if(depth_a > depth_b){
                while(cal_depth(a) > depth_b) {
                    a = (a-2)/K + 1;
                    distance++;
                }
            }

            else {
                while(depth_a < cal_depth(b)) {
                    b = (b-2)/K + 1;
                    distance++;
                }
            }
        }
    }

    public static long cal_depth(long num) {
        if(num<=1) return 0;

        long right = 1;
        long pow = 1;

        while(true) {
            right += (long)Math.pow(K, pow);
            if(num<=right) break;
            pow++;
        }

        return pow;
    }
}