dev-hunmin

www.acmicpc.net/problem/2376 2376번: 단말 정점들의 거리 첫째 줄에 단말 정점의 개수 n(2≤n≤1,000)이 주어진다. 다음 n-1개의 줄에는 차례로 1, 2번 단말 정점 사이의 거리, 2, 3번 단말 정점 사이의 거리, …, n-1, n번 단말 정점 사이의 거리가 주어진다. 다 www.acmicpc.net - 접근법 이진 트리에서 각 단말 정점들의 거리를 가지고 트리 전체를 복원하는 문제이다. 이진 트리는 부모가 자식을 항상 2개씩(왼쪽노드,오른쪽노드)를 가지기 때문에, 단말 정점들의 거리에서 거리가 2인 경우가 항상 존재한다. 단말 정점의 거리가 2라는 것은 같은 부모(조상)을 가지고 있다는 얘기이므로, 이 두 단말 노드들을 공통된 부모(조상)으로 묶어주고 그 노드를 다시..