https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다 www.acmicpc.net 브루트 포스 문제. 가능한 선거구를 모두 찾아서 그것의 (최대-최소)의 최솟값을 계산해주어야 한다. 5번 선거구가 있는 사각형 ..
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 위 5개 도형 중 차례대로 4개는 DFS를 사용해서 간단히 구할 수 있다. 하지만 마지막 'ㅗ' 도형은 DFS로 만들 수 없으므로 ..
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net DP문제 DP[N][L] : N 자리 수에 L 이 올 경우, 오르막 수 조건에 해당하는 경우의 수 ex) DP[3][5] -> _ _ 5 (3번째 자리의 5가 올경우) 점화식: DP[N][L] = DP[N-1][0] + DP[N-1][1] + ... + D..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 문제조건 DP 문제 현재 마실 수 있는 포도주를 wine[i], 현재가 최대일 경우를 저장해놓은 배열을 dp[i]라고 하자. 연속으로..
https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 0은 2와 5의 의해 계산된다. (10 = 2x5) 5의 배수는 2의 배수보다 항상 적으므로 n보다 작은 5의 배수에서 5가 몇번 곱해져있는지 계산하면 된다. 시간을 줄이기 위해, n을 5의 제곱수만큼 나눠주면 5가 총 몇번 들어있는지 바로 알 수 있다. ex) 100/5 = 20 (5의 배수가 총 20번) 100/25 = 4 (25의 배수가 총 4번) => 20+4 = 24 #include using namespace std; int main(){ ios_base::sync_wit..
