[1. 문제 설명]
https://www.acmicpc.net/problem/16562
[2. 풀이 접근]
친구의 친구는 친구다.
- 두 사람이 친구라면, 같은 집합에 묶을 수 있다.
- 유니온-파인드 를 통해 거의 상수 시간에 이 작업이 가능하다.
최소 비용으로 모든 사람과 친구가 되야 한다.
- 유니온-파인드를 통해 각 그룹에는 여러 명의 사람이 존재한다.
- 각 그룹에서 가장 싼 비용만 골라서 비용을 지불하면 된다.
- 단, 남은 비용으로 위 비용을 지불 할 수 없다면 "On no" 를 출력해야 한다.
[3. 코드]
'알고리즘 > Baekjoon' 카테고리의 다른 글
| KMP. [1305] (0) | 2023.03.18 |
|---|---|
| 유니온-파인드. [3197] (0) | 2023.03.16 |
| 유니온-파인드 .[10775] (0) | 2023.03.13 |
| 구간트리. [10999] (0) | 2023.03.10 |
| 구간 트리. [2517] (0) | 2023.03.10 |