BOJ 26216 : 은나무

• 문제 링크 : boj.kr/26216
• 난이도 : G3
• 태그 : 수학, 최소공통조상

---

코드

#include <bits/stdc++.h>

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll k, h, q;
    cin >> k >> h >> q;

    while(q--) {
        ll a, b;
        cin >> a >> b;
        ll ans = 0;
        ll div = k + 1;
        vector<ll> va;
        vector<ll> vb;

        while(a != 0 || b != 0){
            va.push_back(a % div);
            vb.push_back(b % div);
            a /= div;
            b /= div;
        }
        if(vb.size() > h) {
            cout << "-1\n";
            continue;
        }
        for(int i = 0; i < va.size(); i++) {
            if(va[i] != 0) {
                va[i] = -va[i];
                break;
            }
        }
        for(int i = 0; i < vb.size(); i++) {
            if(vb[i] != 0) {
                vb[i] = -vb[i];
                break;
            }
        }
        for(int i = 0; i < va.size(); i++) {
            if(va[i] != vb[i]) ans = (i + 1) * 2;
        }

        for(int i = 0; i < va.size(); i++) {
            if(va[i] != 0) break;
            ans--;
        }
        for(int i = 0; i < vb.size(); i++) {
            if(vb[i] != 0) break;
            ans--;
        }
        cout << max(ans, 0ll) << "\n";
    }

    return 0;
}

---

풀이

은나무는 K+1진법으로 생각해볼 수 있다. 키가 x인 어떤 파란노드를 K+1진법으로 나타내보자. 이 파란 노드의 깊이는 H-(처음으로 나오는 0이 아닌 자리수)이다.

각 흰색 노드의 자식 중 흰색 노드는 0, 1, ... K+1, 파란색 노드는 -1, -2, ... -K라고 하자. 이제 H개의 정수로 특정 노드의 정보를 나타낼 수 있다. 예를 들어 K가 2고 H가 3일때 3은 {0, -1, 0}, 17은 {-2, 2, 1}이다. 이제 공통 조상을 찾는 것은 어렵지 않고, 문제를 해결할 수 있다.