<백준 알고리즘> 11812번 최소 공통 조상, 트리

백준 11812번

접근방법

백준 13116번 이와 비슷한 문제가 존재하는데 여기서는 자식이 최대 2인 경우만 다루는 문제였다.

1. 저 문제에서 아이디어를 차용하여 두 노드 중 현재 크기가 더 큰 노드에 대하여 자신의 부모를 가리키게 하는 방식으로 하나하나 올라가다가 같은 부모를 가리키면 그때까지의 거리가 답이된다.
2. K진 트리이기 때문에 이를 부모를 가리키게 하려면 어떻게 풀어야 하나 생각하였는데 기본적으로 노드의 현재 값을 K로 나눴을때 나머지가 0인 경우와 그 경우의 + 1인 값일 경우 부모는 노드 값 / K가 되고 나머지는 몫에 1을 더해주면 부모를 가리키게 된다.

주의할 점

만약 K가 1인 경우에는 worst case로 시간 복잡도가 10의 15승으로 나오기 때문에 이 경우엔 그냥 두수의 차를 구하면 그게 거리가 된다.

추가

계속해서 제출했는데 시간초과가 나서 이상해서 보니까 cin, cout을 사용할 경우 그런 경우가 난다고 해서 이 코드를 입력하고 제출하니 통과가 됐다.

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>

using namespace std;

int T;
int maxVal = -999;

long long N, K, Q;

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

    cin >> N>>K>>Q;

	map<pair<long long, long long>, int> s;

	while (Q--)
	{
		long long a, b;
		cin >> a >> b;

		int Cnt = 0;

		
		long long maxV = max(a, b);
		long long minV = min(a, b);
		
		if (K == 1)
		{
			cout << maxV - minV << '\n';
			continue;
		}


		while (a != b)
		{
			if (a > b)
			{
				int orig = a;
				a = a / K;

				if (orig % K == 0 || K * a + 1 == orig)
				{
					a = a;
				}
				else
				{
					a = a + 1;
				}
			}
			else
			{
				int orig = b;
				b = b / K;

				if (orig % K == 0 || K * b + 1 == orig)
				{
					b = b;
				}
				else
				{
					b = b + 1;
				}
			}
			Cnt++;
		}

		cout << Cnt << '\n';

	}
	
    return 0;
}