K진 트리 (백준 11812)

안녕하세요. 오늘은 K진 트리를 만들어볼 거예요.

문제

https://www.acmicpc.net/problem/11812

아이디어

이 문제는 그냥 수학문제입니다.

자신의 번호가 A일때 자신의 부모의 번호는 무엇일까요?
그래프를 직접 그려보면 자신의 자식중에서 두번째로 큰 값을 가지는 자식이 자신의 값과 K의 곱이라는 것을 알 수 있습니다. 그런데 자신은 자식을 K개 가지고 있으므로 자식들은 AK-K+2부터 AK+1번까지를 가지고 있음을 알 수 있습니다. 그러므로 어떤 번호가 나오든 그 수에 K-2를 더하면 번호의 범위가 AK부터 AK+K-1이 되므로 여기서 K로 나눠주면 다 A가 됩니다. 그러므로 어떤 노드든지 K-2를 더하고 K로 나누면 부모가 나옵니다.

그런데 K가 2 이상일 때에는 수가 기하급수적으로 작아지면서 시간초과를 피할 수 있습니다. 하지만 K가 1이면 수가 1씩 작아지므로 그냥 두 수의 차를 출력해주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	long long N, K, Q, i, x, y;

	cin >> N >> K >> Q;
	for (i = 0; i < Q; i++)
	{
		cin >> x >> y;
		if (K == 1)
		{
			cout << abs(x - y) << "\n";
		}
		else
		{
			int cnt = 0;
			while (x != y)
			{
				if (x > y) x = (x + K - 2) / K;
				else y = (y + K - 2) / K;
				cnt++;
			}
			cout << cnt << "\n";
		}
	}
}

감사합니다.