https://www.acmicpc.net/problem/17471
17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
조합을 통한 완전탐색 + 유니온파인드로 접근하였다.
접근 방법
입력으로 주어지는 구역의 최대개수는 10이다. 따라서 각 구역이 두 가지 선거구로 선택되는 경우의 수를 계산하면 2^10 즉 1024의 경우의 수가 발생. 이후 각 조건에서 유니온 파인드를 수행한다.
유니온 파인드에서 두 노드가 결합되는 조건은 서로 인접하며 정해진 선거구가 같은 경우만 결합하는 것으로 하였다. 마지막으로 컴포넌트의 수가 2인 경우만 각 선거구의 인구수를 확인하여 정답을 반영하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [13397] 구간 나누기 2 (0) | 2024.02.28 |
|---|---|
| [8983] 사냥꾼 (0) | 2024.02.19 |
| [1700] 멀티탭 스케줄링 (0) | 2024.01.30 |
| [23286] 허들 넘기 (0) | 2024.01.18 |
| [5582] 공통 부분 문자열 (0) | 2024.01.12 |