[BOJ 11812] K진 트리

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

11812번: K진 트리

 

- 문제 요약

 

각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. (1 ≤ K ≤ 1 000)

총 N개의 노드로 이루어져 있는 K진 트리가 주어진다. (1 ≤ N ≤ 10^15)

트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가한다.

아래 그림은 노드 9개로 이루어져 있는 3진 트리이다.

노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

문제에서 주어진 트리는 K진 트리입니다.

주어진 x와 y를 비교하며 부모노드에서 만날 때까지 이동해 주면 됩니다.

 

https://namu.wiki/w/LCA(%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98) 

LCA(알고리즘) - 나무위키

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n,co,a,b;
int k,q;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k>>q;
	for(int i=0;i<q;i++){
		co=0;
		cin>>a>>b;
		if(k==1){
			co=abs(a-b);
		}
		else{
			while(a!=b){
				if(a>b){
					a=(a-2)/k+1;
				}
				else{
					b=(b-2)/k+1;
				}
				co++;
			}
		}
		cout<<co<<'\n';
	}
}

코드 제출 결과