CS/알고리즘 문제 풀이
[백준] 17471 - 게리맨더링 [Python(파이썬)]
문제 www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 역시 삼성 SW A형 문제답게 브루트 포스문제였다. 거기에 그래프 탐색이 더해졌다. 이 문제 또한 2가지의 부분 문제로 나눠볼 수 있다. 1) 선거구를 어떻게 나눌 것인가 2) 어떻게 그래프 탐색을 할 것인가 1) 선거구를 어떻게 나눌 것인가 조합을 사용하여 선거구를 나눈다. 이때 n의 절반(1~n//2)만큼만 조합을 구하면 된다. 이는 mCn = n-mCn이 성립하는 조합의 성질을 잘 생각해보면 알 수 있다. 즉, 한 ..
