백준 11812 : K진 트리

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

11812번: K진 트리

[ 문제풀이 ]

두 노드의 높이를 같게 만든 후 두 노드의 번호가 다르다면 자신의 부모 노드로 올려주면서 두 노드의 번호가 같도록 만들어주면 된다.

핵심은 부모 노드의 번호를 구하는 방법인데 잘 모르겠어서 찾아보니 (자신의 번호 - 2) / K + 1이라고 한다.

주의해야 할 점은 K가 1일 경우다. 이때는 한쪽으로 몰린 트리 형태로 구성되기 때문에 두 노드의 차이를 구해주면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static long N;
	static int K, Q;

	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Long.parseLong(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			Q = Integer.parseInt(st.nextToken());
			for (int i = 0; i < Q; ++i) {
				st = new StringTokenizer(br.readLine());
				long x = Long.parseLong(st.nextToken());
				long y = Long.parseLong(st.nextToken());
				
				if (K == 1) {
					bw.write(Math.abs(x - y) + "\n");
				} else {
					int xH = getHeight(x);
					int yH = getHeight(y);
					long count = 0;
					//1.두 노드의 높이를 같게 만듬
					//2.두 노드의 높이가 같은데 다른 노드면 부모 노드로 올림
					while (xH != yH) {
						if (xH > yH) {
							xH--;
							x = (x - 2) / K + 1;
						} else {
							yH--;
							y = (y - 2) / K + 1;
						}
						count++;
					}
					while (x != y) {
						x = (x - 2) / K + 1;
						y = (y - 2) / K + 1;
						count += 2;
					}
					bw.write(count + "\n");
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static int getHeight(long n) {
		int height = 1;
		long temp = 1, v = 1;
		while (n > temp) {
			v *= K;
			temp += v;
			height++;
		}
		return height;
	}
}