BOJ 2376 단말 정점들의 거리

이 문제는 잘 이해가 안된다.
단말 정점은 자식 정점이 없는 정점을 말하고 문제에서 주어지는 트리는 자식이 없거나 자식이 있다면 두 개의 자식 정점을 가져야하는 이진 트리라고 한다.

그러면 한 가지 형태의 트리밖에 안 나올 것 같은데.. 그리고 또 단말 정점 사이의 거리는 뭔지도 잘 모르겠다... 아.. 백준님의 강의 자료에서 예제 설명을 해놓은 것을 보고 알았다.
한 가지 형태의 트리밖에 나오는 것이 아니다! 그리고, 단말 정점 사이의 거리는 단말 정점 사이의 간선의 개수로 보면된다. 결국 입력으로 주어진 단말 정점 사이의 거리를 이용해서 트리를 만드는 문제이다.

inorder로 탐색을 할 때 단말 정점이 나오는 순서대로 1, 2,...n번으로 번호를 붙여줬다는 것과 어떤 정점에 자식이 있다면 반드시 두 개의 자식(정점)을 갖는다는 점을 활용해보면 트리를 그릴 수 있을 것 같다.

입력으로 1, 2번 사이의 거리, 2, 3번 사이의 거리, ... n-1, n번 사이의 거리가 주어지는데, 입력 순서대로 트리를 그려보면 될 것이다.

예제로 해보면, 1, 2번 사이의 거리가 4인데, 1번이 제일 왼쪽, 2번이 왼쪽에서 두 번째 단말 정점이 되므로 1번의 부모 정점의 바로 오른쪽 자식 정점으로 2번이 붙어야 하는데, 거리가 4이므로 오른쪽 자식 정점의 왼쪽 자식으로 두 번 내려가면 거리가 4가 차이가 난다. 그리고 그렇게 되면 3번은 자연스레 2번의 부모의 오른쪽 자식에 붙게 되는데 그럼 거리차이가 2가 나는 것도 성립한다. 이제 남은 것은 4번인데 4번은 마지막 남은 단말정점 자리(제일 오른쪽)가 될 것이고 그러면 3번과의 거리도 입력처럼 3이 된다. 이제 우리가 구하고자 하는 것은 1, 3번 사이의 거리인데 완성된 트리에서 보면 4만큼 차이가 난다.

이제 이해는 됐는데, 문제는 이것을 어떻게 구현하냐이다.

출처 : 백준님 강의, 강의 자료