반응형
https://www.acmicpc.net/problem/17471
17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
1. 최대 10개인 도시를 두 개의 그룹으로 분리한다.
2. 각 그룹별로 bfs를 돌며, 그룹의 모든 원소가 연결되어 있는지 확인한다.
3. 두 개의 그룹이 전부 연결되어 있다면, 두 그룹 인구수의 차를 구한다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 2018 카카오 recruit - 압축 (Level 2) (0) | 2020.03.03 |
|---|---|
| [Python] 백준 11724. 연결 요소의 개수 (0) | 2020.03.02 |
| [Python] 백준 12100. 2048(Easy) (1) | 2020.02.27 |
| [Python] 백준 1325. 효율적인 해킹 (0) | 2020.02.26 |
| [Python] 프로그래머스. 2020 카카오 recruit - 외벽 점검 (Level 3) (0) | 2020.02.25 |