-
[BOJ - 17779]게리맨더링2백준알고리즘 2020. 2. 9. 16:44
https://www.acmicpc.net/problem/17779
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다
www.acmicpc.net
게리멘더링2, 2019년 하반기 삼성 오전 역량평가 테스트 문제라고한다.
일단.. 풀면서 가장많이 생각난 문제는 SWEA 모의 평가 문제중 디저트 카페라는 문제가 생각이 났다.
대각선을 만들고 그대각선에 따른 경계를 구성해 답을 구해나가는 문제다.
재귀함수가 가장 많이 떠올랐는데..
생각보다 문제가 매우명확하고 충분히 안써도 풀수있겠다는 생각이 들었다.
이 문제를 풀면서 내가 세운 전략은
전제 : 모든 영역의 모든 점에서
경계를 만들고 -> 맵을 구성후 -> 나머지 경계를 만들어서 -> 답을 구해낸다
답이 굉장히 쉽게나오는편이다.
'백준알고리즘' 카테고리의 다른 글
[BOJ - 4217] 신성 문자 (0) 2020.02.14 [BOJ - 14632] 고급 작품 (0) 2020.02.14 [BOJ - 17136]색종이 붙이기 (0) 2020.02.09 [BOJ-17837]새로운 게임2 (0) 2020.02.09 [BOJ-18231]파괴된 도시 (0) 2020.02.09