[백준 / 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] 17383 옥토끼는 통신교육을 풀어라!!
문제 출처 : https://www.acmicpc.net/problem/17383 17383번: 옥토끼는 통신교육을 풀어라!! 옥토끼가 이런 식으로 문제를 풀면 tncks0121은 옥토끼가 5, 10, 15, 20, 25, 30, 34분에 문제를 풀었으므로 최대 5분동안 휴식을 한 것으로 간주한다. www.acmicpc.net 옥토끼는 두개의 문제를 한번에 풀수있다. N개의 문제가 주어질때, 문제를 푸는 시간사이의 공백을 최소화하는 시간을 구하는 문제다. 풀이 결정문제로 풀은 문제였다. Ni가 최대 10억이고, 완전탐색으로 풀경우, 최소 max(Ni)*(a), (a>N)시간복잡도가 나와서, 항상 시간초과가 나온다. 위의 식 N*(a)의 시간을 줄이는 방법은 다음과 같다. 1. N N이 의미하는것은, 모든..
[백준 / 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 증가하며, 패배한 선수의 양쪽 선수와 연결된다. 위 과정을 반복후, 경기장에 혼자 남아있을때, 그 선수를 챔피언 이라고 한다. 이때, 챔피언이 될 가능성이 있는 선수를 모두 구하는 문제다..