백준 11812번 K진 트리

K진 트리

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

3374

860

652

25.894%

문제

각 노드가 자식을 최대 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개의 줄을 출력한다. 각 줄에는 입력으로 주어진 두 노드 사이의 거리를 출력한다.

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
long long n, k, q;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k >> q;
    for(int i=0; i<q; i++) {
        long long low, high;
        cin >> low >> high;
        if (k == 1) {
            cout << abs(low - high)<<'\n';
            continue;
        }

        int cnt = 0;
        while (low != high) {
            while (low>high) {
                cnt++;
                low = (low + k-2)/k;
            }
            while (high > low) {
                cnt++;
                high =(high + k-2)/k;
            }
        }
        cout << cnt << '\n';
    }
    
    return 0;
}

트리 문제를 풀땐 항상 조상노드를 어떻게 타느냐가 핵심이었던것 같다. 하지만 트리문제를 많이 풀어본 편이 아니라서 한 노드당 자식노드의 갯수와 같은 공식?을 잘 몰라서 LCA(최소 공통 조상을 찾는 알고리즘)을 공부한 후에 문제를 풀게 되었다.

핵심 공식은 각 노드의 부모를 구하는 공식인 

(a + k - 2) / k

위공식을 이용해 두 노드의 부모 노드가 같아 질때까지 타고 올라가 그 횟수를 세어주었다. 

주의할점은 k=1일때는 두 노드간의 차이를 구하면 된다는 점이다