복습노트 복습노트

문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net n개의 노드와 간선정보가 주어지면, 위와 같이 빨간색 부분과 파란색 부분을 나누어, 빨간색 부분의 합과 파란색 부분의 합의 최솟값을 구하는 문제입니다. 물론 각 노드마다 값은 주어집니다. 또한 같은 부분에 속하는 모든 노드는 서로 연결되어 있어야 합니다. 1) 일단 빨간색, 파란색 부분을 나누는 경우의 수, 즉 조합을 생각해야 합니다. 2) 부분을 나눴으면, 나눈 부분들이 실제로 가능한지 판별해야 합니다. 2-1) 부분은 최소 1개의 노드를 가져야합니다. 2-2) 부분에 속하는 ..

문제 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net n개의 집 위치의 x좌표와 c개의 공유기가 주어지면 거리를 최대로 늘리면서 c개의 공유기를 집에 적당히 설치했을 때 최대 거리를 구하는 문제입니다. https://st-lab.tistory.com/277 여기서 문제를 자세히 살펴보시면 됩니다. 간단한 이분탐색 문제이지만, 이분탐색에 구현에 있어서 힘들었던 문제입니다. int l = 1; int r = *max_element(v.begin(), v.end(..

문제 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net S(0) = "moo" S(1) = S(0) + mooo + S(0) S(2) = S(1) + moooo + S(1) ... 위와 같은 moo 수열이 있습니다. 이 때 n이 주어지면, n번째 글자를 출력하면 되는 문제입니다. moo수열은 무한대입니다. n > n; moo(n, 0, ans.length()); } 이제 위에서 설명한 것은 코드로 구현하겠습니다. void moo(int i, int step, int init)..

문제 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 3 * n 행렬을 (2*1) 타일과 (1*2) 타일로 채우는 경우의 수를 구하는 문제입니다. 위의 예시는 n =12 인데 이런식으로 채우면 됩니다. 생각해 보면 n =홀수 이면 타일을 채울 수 없습니다. 먼저 n = 2이면 총 3가지로 타일을 채울 수 있습니다. 따라서 dp[2] = 3입니다. n = 4이면 반으로 갈라서 dp[4] = dp[2] * dp[2] 일거 같지만, 아닙니다. 특별한 경우가 있습니다. 위의 두가지 경우의 수는 dp[2]의 타일들로 만들 수 없습니다. 따라서 dp[4] = dp[2] * dp[2] + 2 = 11입니다. 그러면 dp[6]은 어떨..

문제 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net n개의 전깃줄이 주어지면 전깃줄이 겹치지 않게 주어진 전깃줄을 최소로 제거해야 되는 문제입니다. 즉, 최소로 제거할 전깃줄의 개수를 구하는 문제입니다. 예를 들어 왼쪽의 그림처럼 전깃줄이 주어진다면 , , 를 제거하거나 , , 를 제거하면 모든 전깃줄이 엉키는 부분이 없어집니다. 즉, 3개의 전깃줄을 제거하면 됩니다. 일단 입력부분을 보면 알겠지만, A부분의 전깃줄이 오름차순으로 차례대로 주어지지 않습니다. 그리고 전깃줄의 시작점을 A라 하고, 끝점을 B라 하면..

문제 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net n개의 동전이 주어지면 동전의 조합을 이용해 k원이 되는 경우의 수를 구하는 것입니다. 동전은 무한대로 쓸 수 있습니다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우입니다. 예를 들어 n = 3이고 동전의 가치가 각각 1, 2, 5이고 k = 10이면 동전의 조합을 통해 10이되는 경우의 수는 10입니다. 처음에 봤을 떄 knapsack 문제와 비슷한 느낌을 받아 이차원 배열을 만들고 생각해봤습니다. 먼저 1원으로 1 ~ 10원을 만드는 경우의..

문제 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net n일의 여름방학이 주어지고, m번의 바쁜날이 주어지면 여름방학동안 리조트 이용을 바쁜날을 제외하고 매일 할 떄 최소비용을 구하는 문제입니다. 위의 표의 첫번째 행은 여름방학의 날을 의미합니다. 검은색은 바쁜날입니다. 두번째 행과 세번째 행은 각각 비용입니다. 두번째 행은 7만원이 들고, 세번째 행은 62000원이 들어서 최소비용은 62000원입니다. 쿠폰을 3개 모으면 하루 이용권이 무료로 제공됩니다. 쿠폰의 여부에 따라 최소비용을 결정하는 것이 까다로웠습니다. 그래..

문제 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 위와 같은 괄호가 주어졌을 때, 괄호가 바로 ()이면 레이져이고, '('는 쇠막대기의 시작점, ')'는 쇠막대기의 끝점입니다. 레이져를 쏘았을 때 쇠막대기의 조각을 세는 문제입니다. 위의 그림에서는 17개 입니다. 처음에는 레이저의 좌표와 쇠막대기의 좌표를 기록해 하나하나 비교해가면서 레이져가 쇠막대기를 겹치는 부분을 세었습니다. 물론 정답은 맞았지만, 시간이 매우 오래 걸렸습니다. (O(n^2)) 새로운 방법은 '(' 가 나오면 무조건 스택에 넣어줍니다. 그러다가 레..