[백준 / BOJ] 17471 게리맨더링
문제 출처 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net N개의 선거구와 각 선거구에 사는 인원수가 주어진다. 선거구는 2개의 선거진영으로 나뉘며, 이때, 각 선거진영 선거진영 별로 모두 연결되어있어야한다. 이때, 선거진영의 인구수 차이를 최소화하는 값을 구하는 문제다. 풀이 비트마스킹을 이용한 완전탐색으로 푼 문제다. 처음엔 비트마스킹 + 백 트래킹으로 생각했으나, 이 방법으로는 모든 경우를 봐주지 못해서 풀기 힘들어 보였다. 알고리즘은 다음과 같다. 1. ..
[백준 / BOJ] 21319 챔피언(Easy)
문제 출처 : https://www.acmicpc.net/problem/21319 21319번: 챔피언 (Easy) 1번 선수는 어떻게 해도 챔피언이 될 수 없다. 2번 선수는 어떻게 해도 챔피언이 될 수 없다. 3번 선수는 (2, 3), (1, 3), (3, 4) 순서대로 격투가 일어나면 챔피언이 될 수 있다. 4번 선수는 (3, 4), (2, 4), www.acmicpc.net N명의 선수가 비 내림차순으로 주어진다. 각 선수는 자신의 양쪽선수와 경기를 하며 파워가 더 쌘 선수가 승리한다. 승리시 자신의 파워가 +1 증가하며, 패배한 선수의 양쪽 선수와 연결된다. 위 과정을 반복후, 경기장에 혼자 남아있을때, 그 선수를 챔피언 이라고 한다. 이때, 챔피언이 될 가능성이 있는 선수를 모두 구하는 문제다..