https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 크루스칼 알고리즘 문제 조건 도시가 연결되어 있는 단위를 (도시 한 개만 존재하는 단위도 포함) 도시 묶음이라 하자. 이 도시 묶음 하나 당 발전소는 단 한 개가 존재해야 한다. (MST에서) 두 노드가 같은 트리 안에 존재할 수 없다는 건 두 노드의 부모노드가 같다는 뜻이다. 따라서 발전소의 부모노드를 통일시킨다 (union한다) 발전소 중 하나의 노드..

https://www.acmicpc.net/problem/2180 2180번: 소방서의 고민 첫째 줄에 화재 발생 건수 n이 주어진다. n은 200,000 이하의 양의 정수이다. 둘째 줄부터 n개의 줄에 각각 한 줄에 한 쌍씩 a와 b가 입력된다. a와 b는 40,000 이하의 음이 아닌 정수이다. www.acmicpc.net 문제 이해 문제의 입출력을 보자. 입력 3 2 0 1 2 0 3 출력 5 운이 좋게도 주어진 입력 예시 순서를 따라가면 출력이 나온다. 화재를 진압하는데 걸리는 시간은 at + b이므로 1번째 소방서에서 0초 소비, (2 * 0 + 0) 2번째 소방서에선 2초 소비, (1 * 0 + 2) 3번째 소방서에선 3초 소비 (0 * 2 + 3) 하므로 총 5초(정확히는 단위 시간) 이 소..