DFS조합

[백준 17471] 게리맨더링 C++

www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 이 문제는 브루트포스 문제로, 모든 경우의 수를 다 시뮬레이션 돌려보고, 문제의 조건에 맞다면 경우의 수를 +1 해줍니다. 브루트포스 문제라고 생각했던 이유는 바로, N의 제한이 10밖에 안됐기 때문입니다. 조합을 구하는데 시간복잡도는 약 O(2^N)으로, 2의 10승은 1024이고, 노드가 1개 이상일 때부터 조건이 가능하니까 때문에 2^10승 * 10정도로 생각했습니다. 원리는 두 개의 집단으로 나누면 되는데, DFS 조합을 구..