우선 두 노드 사이의 거리를 구하기 위해서는 LCA를 구해야 하는데, 다른 문제와 달리 Segment Tree나 다른 기법을 사용하지 않고도 K진 트리의 기본 속성을 이용해 LCA를 구할 수 있다. 공식은 다음과 같다.
P = (N-2)/K + 1
(P: Parent Node / N: Child Node / K: Degree)
그런데 다른 블로그들을 보니 공식만 나와 있고 증명이나 유도 과정이 없어, 이 글에선 공식 유도 과정까지 다뤄보려 한다. 우선 K진 트리는 다음과 같은 형태로 나타난다.
- S : 루트 노드
- l : i 번째 높이에서의 왼쪽 끝 노드
- P : 임의의 부모 노드
- C : P의 자식 노드 집합 (k개)
여기서 우리가 관심 있는 것은 C의 값을 이용해 P를 나타낼 수 있느냐이다. 우선 l를 이용해 P와 C를 표현해보자.
이때 l(i)와 l(i+1)의 관계를 통해 l의 점화식은 다음과 같이 나타낼 수 있다.
이 식을 C에 대입하면 다음과 같이 P가 포함된 식으로 변형할 수 있다.
이때 S는 실제로 1이므로 대입 후, P에 대한 식으로 나타내면 다음과 같다.
그런데 아직까지도 처음 언급한 식의 형태가 나오지 않는다. 바로 -Θ/k 때문이다. 여기서 살펴볼 점은 P는 자연수라는 점이다. 따라서 좌변이 자연수이니 우변에서도 1을 제외한 (C-2)/k - Θ/k가 자연수여야 한다. 이 점을 고려해 다음과 같이 식을 표현할 수 있다.
즉 실제로 수학적으로 구해진 C와 P에 대한 공식은 다음과 같다.
하지만 프로그래밍 언어의 특성 상 나눗셈 시 자동으로 버림 처리가 되기 때문에 다음이 성립하게 되는 것이다!
이제 공식이 증명됐으니 실제로 코드를 작성해보면 O(lgn)의 복잡도로 문제 해결이 가능하다. 참고로 K가 1일 때는 P=N-1이 되어 O(N)의 복잡도를 갖게 되므로 예외처리를 해주지 않으면 시간 초과가 발생한다.
// https://www.acmicpc.net/problem/11812
import java.io.*;
import java.util.*;
class Solution{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
long N;
int K, Q;
public Solution() throws IOException {
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");
continue;
}
long cnt = 0;
while(x != y){
long max = Math.max(x, y);
y = Math.min(x, y);
x = (max-2)/K + 1;
cnt++;
}
bw.write(cnt+"\n");
}
bw.close();
}
}
public class Main {
public static void main(String[] args) throws IOException {
new Solution();
}
}
출처: 오지는 컴퓨터 공부
댓글 (1개) 댓글 쓰기
jameswebb 3년 전
오.. 감사합니다!