문제 https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 풀이 solved.ac 난이도: Platium5 [백준] 평범한 배낭(12865)의 다음 단계 문제로 같은 물건이 여러 개 있는 경우이다. 이 문제를 일반적인 배낭(Knapsack) 문제와 동일하게 해결하려 시간 복잡도가 O(N* K *M)이기 때문에 시간 초과가 발생한다. 따라서 다음과 같은 최적화가 필요하다. 물건의 개수를 2의 제곱수의 합으로 분..

문제 https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 높이 순서로 정렬 후, 해당 그림이 선택될 수 있도록 하는 앞의 그림들 중 가장 높은 그림을 미리 저장해 두자. 이를 저장하는 이유는 다음과 같은 점화식을 구현하기 위해서 이다. dp[idx]를 idx번째 그림까지를 고려했을 때, 판매 가능한(선택된) 그림의 가격 합의 최대 값이라 고하자. dp[idx]를 구할 때 두 가지 경우를 고려해..

문제 https://www.acmicpc.net/problem/2570 2570번: 비숍2 첫째 줄에 정사각형 체스판의 크기 N이 주어진다. 둘째 줄에는 체스판 위에 놓인 장애물의 개수 M이 주어진다. N은 100이하의 자연수이고 M은 음이 아닌 정수이다. 이어 셋째 줄부터 한 줄에 하나 www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 이분할 집합에 대해 곰곰이 생각해봐야 풀 수 있는 이분 매칭 문제. 한 좌표에 비숍을 놓으면 해당 비숍에 의해 더 이상 다른 말을 놓을 수 없는 두 대각선이 생긴다. 하지만 좌표와 두 대각선을 이분 매칭을 진행하는 것은 불가능하다. (하나의 좌표에 대각선을 두 개 매칭해 주어야하기 때문에) 따라서 방향이 다른 대각선끼리 집합을 만들어 이분 매..

문제 https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 짝수와 홀수로 두 집합을 만들어 이분 매칭으로 해결하는 문제. 이분 매칭을 잘 모른다면 다음 기본 문제를 먼저 해결해보고 오자. [백준] No.2188 - 축사 배정 (C++, 이분 매칭) 두 자연수를 더하는 경우는 3가지로 분류할 수 있다. 1. 짝수 + 짝수 짝수끼리 더한 수는 짝수이기 때문..

문제 https://www.acmicpc.net/problem/9577 9577번: 토렌트 희원이가 사용하는 ACM토렌트는 하나의 파일을 공유받을 때 여러 조각으로 나누어, 조각을 지닌 시드가 접속하는 시간에 시드로 부터 일부 조각을 전송 받아 파일을 완성시키는 방법으로 파일이 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 두 집합의 대응 관계를 해결하는 이분 매칭 문제. 기본 적인 이분 매칭 문제를 해결하고 오면 이해하기 쉬울 것이다. [백준] 축사 배정(2188) 이번 문제에서 두 집합으로 선택되는 것은 시간(A set)과 조각(B set)이다. 파일이 어떤 시더에게 있는지는 상관없이, 접속 시간에 해당 파일을 다운로드할 수 있는 여부가 중요하기 때문이다. 따라서 시더..

문제 https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 이분 매칭 문제들은 최대 유량을 이용하면 간단히 해결할 수 있다. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 이분 매칭 문제는 두 집합에서의 대응 관계를 해결할 수 있다. 대표적으로 작업 배분을 한다고 생각해보자. A집합(인원)이 할 수 있는 B집합(작업)들 중 하나 선택하여 배정받는다. 이때 최대한의 작업을 할 수..

문제 https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 그래프 모델링이 필요한 최대 유량 문제. 문제의 설명에서는 연산을 한 번씩 진행하여 각 정수를 1씩 줄이지만 생각해보면 어떤 정수끼리 짝을 짓는 가는 중요하지 않다. 예제의 입력을 생각해보면 어떤 짝이든 짝지은 두 정수를 최대한 줄여주면 결과는 동일하다. 여기서 연산을 한번 진행할 때 전체 값의 합은 2씩 줄어드는..

문제 https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 정점 분할 테크닉을 통해 풀어야 하는 최대 유량 문제. 최대 유량에 대해서 잘 모른다면 다음 게시글을 참조하자. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 정점 분할이란 정점에도 간선처럼 가중치를 주기 위해 정점을 하나의 간선으로 만드는 기법이다. 이때 간선을 정점처럼 취급하기 위해 정점을 두개의 정점..

문제 https://www.acmicpc.net/problem/1420 1420번: 학교 가지마! 첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 최소 컷 (최대 유량)알고리즘에 정점 분할을 적용해야 하는 문제. 정점 분할이란 정점에도 간선처럼 가중치를 주기 위해 정점을 하나의 간선으로 만드는 기법이다. 이때 간선을 정점처럼 취급하기 위해 정점을 두개의 정점(in과 out)으로 분할 한다. in정점은 해당 정점으로 들어오는 간선들과 연결해주고 out정점..

문제 https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 이름부터가 최대 유량인 최대 유량 문제. 최대 유량 알고리즘과 이번 풀이의 기본 지식을 알기 위해 다음 게시글을 참고 하자. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 기본적인 최대 유량 알고리즘을 적용하기에는 약간 다른 점이 있는데 파이프는 양방향으로 존재하고 같은 두 정점이 여러 간선으로 이어질..