[백준] 17779 게리 맨더링 2
2020. 2. 22. 14:58
https://www.acmicpc.net/problem/17779
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다
www.acmicpc.net
완전탐색 문제 였습니다.
경계설정하기가 까다로워 보이지만 주어진 조건을 그대로 구현하면 경계설정은 생각보다 간단했습니다.
문제에 주어진 조건을 그대로 따라 순차적으로 구현해주면 됩니다.
문제 풀이
- 기준점을 선별한다. 문제에 제시된 조건을 활용
- 경계선을 따라 그리고 경계선 안쪽에 있는 5번구역을 먼저 masking해준다.
- 5번구역을 제외한 나머지 1,2,3,4구역을 masking한다
- masking된 맵을 사용해 각 지역의 인구수 총합을 계산하고, 인구차이의 최소값을 업데이트 한다.
조건들은 문제에 주석처리 하였습니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 11057 오르막 수 (DP) (0) | 2020.02.27 |
|---|---|
| [백준] 15686 치킨 배달 (Brute force) (0) | 2020.02.23 |
| [백준] 16234 인구 이동 (0) | 2020.02.18 |
| [백준] 16235 나무 재테크 (0) | 2020.02.18 |
| [백준] 17837 새로운 게임 2 (0) | 2020.02.15 |