https://www.acmicpc.net/problem/22967
요약
- 트리가 주어지고
- 최대 n - 1 개 간선을 추가하여 지름을 최소화하기
- 지름 : 가장 먼 노드간의 거리
- n <= 300
접근법
- 아이디어가 막막했으나, 티어를 보고 힌트를 얻음
- 최선을 다해서 지름을 1로 만들려면 어떻게 해야하나?
- 각 노드를 서로 연결한다
- 필요한 간선은? n * (n - 1) / 2개
- n = 4 : 6개 ==> 가능
- n = 5 : 10개 ==> 불가능
- 모든 노드를 연결하지 못할때의 최선은? 한 노드에 연결하는 star형 구조 ==> 1번 노드를 제외하고 나머지 노드를 2번 노드에 연결하면 됨 ==> 최대 n - 1
- 트릭을 떠올려야하는 문제라 쉽지 않았음
newbieski