boj 11812: K진 트리

k진 트리에서 두 노드 사이의 거리를 구하는 문제이다.

공통 조상문제와 유사한데, 각 노드에서 공통 조상까지의 거리를 구한 뒤 더하면 된다.

주의할 점은 노드의 수가 10^15이므로 long 타입을 사용해야 한다.

이때 k == 1인 경우는 트리의 높이가 log단위가 아니고 한 개로 쭉 나열 되어 있으므로 따로 먼저 높이 차를 리턴해주면 된다.

​

k진 트리를 보면서 규칙을 찾아보자

정점 long A의 부모노드가 (A-2)/k + 1임을 알 수 있다.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long n = in.nextLong(); // 노드 수
		int k = in.nextInt(); // k진 트리
		int test = in.nextInt();

		for (int t = 0; t < test; t++) {
			long x = in.nextLong();
			long y = in.nextLong();

			if (k == 1) {
				System.out.println(Math.abs(x - y));
				continue;
			}

			long distance = 0;
			while (x != y) {
				long max = Math.max(x, y);
				y = Math.min(x, y);
				x = (max - 2) / k + 1;
				distance++;
			}
			System.out.println(distance);
		}
	}
}

 

2021/01/17 - [알고리즘 공부] - SWEA 1248: 공통조상