[BOJ - 11812] K진 트리

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

11812번: K진 트리

아 .. 열심히 작성된 글이 지워져서 처음부터 다시쓴다.

문제 자체의 숫자 범위가 굉장히 크기때문에 일반적인 DFS를 쓰기에는 무리라고 생각했다.

그래서 주어진 값들의 부모를 찾아가서 이들이 만나는 위치를 직접 탐색하고 확인해서

결과를 내는 방법에 착안했다.

규칙성이 한가지 있는데

1을 제외한 어떤 노드라고 하더라도

해당 노드 의 K에 대한 나머지가 1 또는 0 일때는 K로 나눈 몫이 부모 노드가 되고, 그렇지 않다면 몫의 +1 값이 부모 노드가 된다.

이러한 점을 착안해서 쭉 올라간것을 arr을 통해 기록한다.

이때 기록된 배열은 굉장히 특이하게도 역 정렬된 배열이된다.

그 다음 탐색할 숫자를 첫번째 노드가 탐색한것처럼 탐색 하지만, 검색 할때마다 첫번째 값에 대해 부모노드를 기록한 배열에서

이분 탐색을 진행하면서 그 해당 레벨을 찾고 답을 도출한다.