[백준 11812] K진 트리

분류 : dfs

 

요구사항

K진 트리에서 주어진 두 숫자 간의 거리 구하기

 

풀이

이진 트리에서 자식은 node*2, 부모는 node/2이다

3진 트리는

1

2          3 4

5 6 7

4진 트리는

1

2                 3 4 5

6 7 8 9

5진 트리는

1

2                   3 4 5 6

7 8 9 10 11

 

자식은 node*k+1까지가 자식이다

부모는 (node+(k-2))/k이다   (k-2)인 이유는 node*k+1까지가 자식이기 때문이다

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
ll n, k, q;
ll parent(ll x, ll y) {
	return (x + y - 2) / y;
}

int main() {
	scanf("%lld %lld%lld", &n, &k, &q);
	for (int tc = 0; tc < q; tc++) {
		ll low, high;
		scanf("%lld%lld", &low, &high);
		if (k == 1) {
			printf("%lld\n", abs(low - high));
			continue;
		}

		int cnt = 0;
		while (low != high) {
			while (low>high) {
				cnt++;
				low = parent(low, k);
			}
			while (high > low) {
				cnt++;
				high = parent(high, k);
			}
		}
		printf("%d\n", cnt);
	}


}