문제
각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다.
트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다.
아래 그림은 노드 9개로 이루어져 있는 3진 트리이다.
노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 <= N <= 10^15)과 K (1 <= K <= 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 <= Q <= 100 000)가 주어진다.
다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 <= x, y <= N, x ≠ y)
출력
총 Q개의 줄을 출력한다. 각 줄에는 입력으로 주어진 두 노드 사이의 거리를 출력한다.
풀이
처음에는 트리를 실제로 만들어서 부모를 타고 올라가고 싶어지지만, N의 범위가 10^15라서 그 방법은 애초에 불가능하다. 그래서 현재 노드의 부모 번호를 직접 계산하는 방법이 필요하다.
이 트리는 각 레벨이 왼쪽부터 순서대로 채워지기 때문에, 노드 번호와 부모 번호 사이에 일정한 규칙이 있다. 루트를 1번이라고 하면, 어떤 노드 x의 부모는 (x - 2) / K + 1로 바로 구할 수 있다. 즉 트리를 만들지 않고도 부모 방향으로 올라가는 연산은 할 수 있다.
두 노드 사이의 거리는 결국 공통 조상에서 만날 때까지 더 큰 번호 쪽을 부모로 계속 올리면 구할 수 있다. 코드에서는 x != y인 동안 더 큰 쪽을 getParent()로 올리고, 한 번 올릴 때마다 거리 카운트를 증가시킨다.
예외는 K = 1일 때다. 이 경우 트리가 아니라 1번부터 N번까지 일직선으로 이어진 형태가 되므로, 두 노드 사이의 거리는 그냥 |x - y|가 된다.
그리고 N이 10^15까지 가능하므로 int는 당연히 부족하다. 노드 번호와 답 계산은 long long으로 처리해야 안전하다.
코드
#include <iostream>
#include <cmath>
using namespace std;
long long n;
int k, q;
long long getParent(long long x) {
return (x - 2) / k + 1;
}
long long solve(long long x, long long y) {
if (k == 1) return abs(x - y);
long long ans = 0;
while (x != y) {
if (x > y) x = getParent(x);
else y = getParent(y);
ans++;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k >> q;
long long x, y;
while (q--) {
cin >> x >> y;
cout << solve(x, y) << '\n';
}
return 0;
}복잡도
- 시간 복잡도: 트리 높이를 라 하면 질의마다 두 노드를 위로 올리므로 이다.
- 공간 복잡도:
마무리
트리 문제라고 해서 항상 트리를 직접 만들 필요는 없다. 번호가 채워지는 규칙만 이용할 수 있다면, 부모를 수식으로 구해서 훨씬 가볍게 처리할 수 있다.
