백준(boj)11812 - K진 트리

문제 링크 - https://www.acmicpc.net/problem/11812

👀문제이해 및 풀이방법

간만에 어려운 문제를 만나서 고민한 결과를 남겨놓기 위해 적는다. 이전글인 lca알고리즘을 적고 lca문제를 푸는데 골드문제인데도 상당히 어려웠다
k진 트리에서 depth와 parent를 구하여 결국 lca를 구하는 문제인데 sparse배열을 사용하지 못하였고 (노드의 개수가 10의 15승개라 도저히 저장할 수 없다)
depth를 구하는 방법이 상당히 특이하여 알아내기가 너무 어려웠다

결국 글을 찾아보았고 위와같은 트리의 형태를

노드를 0번부터 시작하도록 생각하여 depth는 값에 k배를 하고 left는+1 right는 +K로 하면 depth의 규칙이 나온다는 것을 알게되었다
또한 parent노드는 값에 -1를 하고 k로 나누어 주면 나오게 된다 (n-1)/K

평범하지 않은 규칙을 2개나 찾아야하고 인덱싱이 -1로 된다는 점, 개수가 너무 많아 저장을 하지 못한다는 점을 고려해 보면 상당히 난이도가 있게 느껴졌다

📝코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
class tree_length{
private:
    ll N,K;
public:
    tree_length(){
        std::cin >> N >> K;
    }
    ll get_depth(ll n){
        ll depth=0;
        if(K==1)
            return n;
        if(n!=0){
            depth=1;
            ll left=1,right=K;
            while(!(left<=n && n<=right)){
                depth++;
                left = left*K +1;
                right = right*K +K;
            }
        }
        return depth;
    }

    ll lca(ll a, ll b){
        ll depth_a=get_depth(a);
        ll depth_b=get_depth(b);
        if(depth_a>depth_b){
            swap(depth_a,depth_b);
            swap(a,b);
        }
        if(K==1)
            return depth_b-depth_a;
        ll sol = depth_b-depth_a;
        for(int i=0;i<sol;i++)
            b=(b-1)/K;
        while(a!=b){
            a=(a-1)/K;
            b=(b-1)/K;
            sol+=2;
        }
        return sol;
    }


};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n,a,b;
    tree_length tl;
    std::cin >> n;
    for(int i=0;i<n;i++){
        std::cin >> a >> b;
        std::cout << tl.lca(a-1,b-1)<<'\n';

    }

    return 0;
}