11812 K진 트리 문제 공식의 수학적 증명

11812 K진 트리

우선 두 노드 사이의 거리를 구하기 위해서는 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개)

Imgur2

여기서 우리가 관심 있는 것은 C의 값을 이용해 P를 나타낼 수 있느냐이다. 우선 l를 이용해 P와 C를 표현해보자.

Imgur3

이때 l(i)와 l(i+1)의 관계를 통해 l의 점화식은 다음과 같이 나타낼 수 있다.

Imgur4

이 식을 C에 대입하면 다음과 같이 P가 포함된 식으로 변형할 수 있다.

Imgur5

이때 S는 실제로 1이므로 대입 후, P에 대한 식으로 나타내면 다음과 같다.

Imgur6

그런데 아직까지도 처음 언급한 식의 형태가 나오지 않는다. 바로 -Θ/k 때문이다. 여기서 살펴볼 점은 P는 자연수라는 점이다. 따라서 좌변이 자연수이니 우변에서도 1을 제외한 (C-2)/k - Θ/k가 자연수여야 한다. 이 점을 고려해 다음과 같이 식을 표현할 수 있다.

Imgur7

즉 실제로 수학적으로 구해진 C와 P에 대한 공식은 다음과 같다.

Imgur8

하지만 프로그래밍 언어의 특성 상 나눗셈 시 자동으로 버림 처리가 되기 때문에 다음이 성립하게 되는 것이다!

Imgur9

이제 공식이 증명됐으니 실제로 코드를 작성해보면 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년 전

오.. 감사합니다!