17471 게리맨더링
-
백준 17471 게리맨더링Algorithm/BOJ 2021. 3. 28. 21:02
출처: www.acmicpc.net/problem/17471 분류: 완전탐색 접근방식 n이 최대 10밖에 안 되기 때문에 완전탐색으로 해결할 수 있었습니다. 각 구역을 0, 1 중 하나가 되는 조합을 뽑아서 해당 조합이 조건을 만족하는지 확인하는 방식으로 해결했습니다. 풀이를 떠올리는 건 어렵지 않았는데 구현에서 꽤나 시간을 잡아먹었네요.. 때문에 하나씩 차근차근 살펴보면서 정리해보겠습니다. 먼저 각 구역의 인구, 인접 구역, 파티(정당), 최소 차이 를 담을 변수들이 필요했습니다. 구역의 최대 인구가 100이기 때문에 모든 구역의 인구가 100이여도 차이는 1000을 넘지 않습니다. 초기값은 그냥 여유롭게 10000으로 잡아줬습니다. var population: [Int] = [0] var adjace..