[백준] 22967. 구름다리

newbieski·3일 전
0

백준

목록 보기
52/52

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
  • 트릭을 떠올려야하는 문제라 쉽지 않았음
profile
newbieski

0개의 댓글