삼성 a형 문제
-
[BOJ] #17471 _ 게리맨더링Problem Solving/BOJ 2019. 10. 22. 22:13
[게리맨더링] https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 두 구역으로 나눌 수 있는 모든 경우의 수를 고려하여 인구 차이의 최솟값을 구하는 문제이다. next_permutation을 통해 구현하였다. 알고리즘의 흐름은 다음과 같다. 1. 경우의 수 만들기 (1:N, 2:N-2 ...) 2. 각 구역의 연결 유무 확인 3. 두 구역 모두 연결되어 있다면, 인구 수 차이 구하기 checkConnection()의 매개변수인 type은 1구역 2구역을 나타내는 변수이..