[BOJ | 백준] 11812번: K진 트리

by Kimcoding on 2020-03-18 20:53

in BOJ

문제 설명

BOJ 11812

K진 트리가 주어졌을 때 입력받은 두 노드의 거리를 구하는 문제입니다.

풀이

두 노드의 거리를 구하려면 두 노드의 최소 공통 조상까지의 깊이를 더하면 됩니다.

K진 트리 노드 번호들이 순서대로 주어집니다.

번호가 A < B 라면 B가 A보단 깊이가 깊거나 같기 때문에 B를 부모 노드로 이동하고 아니면 A를 부모 노드로 이동합니다.

K진 트리 노드의 부모 노드는 (자식 노드 - 1) / K로 구할 수 있습니다. (루트가 0일때)

문제에서 루트가 1이지만 아주 조금 더 깔끔하게 식이 나오길래 루트를 0으로 잡고 풀었습니다. (갑자기 그러고 싶었습니다…)

하고 싶은대로 하시면 됩니다!

시간 복잡도는 O(\(log_kN\))인데 K가 1일 때는 O(N)이 되므로 예외처리를 해서 바로 거리를 구하시면 됩니다.

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, a, b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;

int main() {
    FIO;
    ll n, k,q;
    cin >> n >> k >> q;
    while(q--){
        ll a, b;
        cin >> a >> b;
        a--, b--;
        if(k == 1) {
            cout << abs(a-b) << '\n';
            continue;
        }
        ll val = 0;
        while(a != b){
            if(a < b) b = (b - 1) / k;
            else a = (a - 1) / k;
            val++;
        }
        cout << val << '\n';
    }
    return 0;
}