티스토리 뷰
https://www.acmicpc.net/problem/11812
11812번: K진 트리
첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y
www.acmicpc.net
처음에 k진 트리의 각 depth 별 마지막 노드가 k^n + k^(n-1) + ... + 1 번이 됨을 이용하여 각 노드의 부모를 찾은 뒤 그 부모 노드로부터 또다시 부모 노드를 찾는 방법을 시도하였지만 10% 정도 맞춘 뒤 시간초과가 계속 나와 다른 방법으로 풀었습니다.
(생각하면 할 수록 무한루프 도는 구간이 발견되어 때려치웠다....)
생각보다 간단하게 해결할 수 있었습니다. n 이라는 노드의 부모노드는 (n -2)/k + 1 이 됩니다. (이걸 왜 몰랐을까....)
이를 이용해 두 노드 중 더 깊이 있는 노드 (값이 더 큰 노드)를 기준으로 부모로 업데이트하며 부모가 일치하면 종료하면 됩니다. 이 때 부모노드로 올라간 횟수를 카운트하면 정답이 됩니다.
k= 1의 경우 리스트와 같은 형태의 트리이므로 그냥 빼기를 해주면 됩니다.
정답은 다음과 같습니다.
댓글