[BOJ] 11812 - K진 트리

문제 출처

[BOJ] 11812 - K진 트리

 

풀이

자식을 최대 K개 가질 수 있는 K진 트리에 있는 노드들 중 주어진 두개의 노드 사이의 거리를 구하는 문제였습니다.

 

두개의 노드가 주어지면 해당 노드의 부모노드를 찾고, 부모노드의 부모노드를 찾는 과정을 쭉 반복하면서 루트노드인 1을 만날때 까지 저장해주어 저장해준 값을 비교하면서 부모노드가 달라지는 경우를 판단해 거리를 구해주었습니다.

 

부모노드를 찾는 수식은 다음과 같습니다.

 

부모노드 = (현재 노드 + K -2) / K 

 

코드

small-j/Algorithm