시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 (하단 참고) | 1024 MB | 390 | 195 | 137 | 45.819% |
여섯 다리만 건너면 전 세계의 모든 사람을 알게 된다는 이론이 있다. 이렇게 모든 사람이 여러 다리를 건너 알게 된 상황을 떠올려보자.
서로 모르는 $N$명의 사람이 있다. 이들은 각각 $1$번부터 $N$번까지 번호가 매겨져 있다. 이들 중 둘은 함께 식사를 하여 서로 친구가 될 수 있다. 음식의 가격은 다음과 같이 정해진다.
'친구의 친구', '친구의 친구의 친구' 등을 '건너 아는 사이'라고 한다. 즉 친구 사이인 두 사람을 모두 연결해 그래프로 나타낼 때, $u$번 정점에서 $v$번 정점으로 가는 경로가 존재한다면 $u$번과 $v$번은 '건너 아는 사이'이다. $u$와 $v$가 친구일 때도 경로가 존재하므로, 친구 사이인 두 사람도 '건너 아는 사이'이다.
$N$명의 사람은 서로 친구가 되어 결국 모든 쌍의 사람이 '건너 아는 사이'가 되었다. 이들은 음식의 가격의 합이 최소가 되도록 서로 '건너 아는 사이'가 되었을 때, 그 가격의 합을 구하는 프로그램을 작성하시오.
입력은 아래와 같이 주어진다.
$N$
첫째 줄에 비용의 최솟값을 출력한다.
5
12
University > 연세대학교 > 2022 연세대학교 프로그래밍 경진대회 E번