αλγριθμο

문제 https://www.acmicpc.net/problem/2647 2647번: 검은점과 하얀점 연결 2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점이다. 하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다. 한 쌍의 점 www.acmicpc.net 알고리즘 DP 풀이 DP 역추적 문제입니다. 점들에 대한 정보가 주어졌을 때, 다음 \(3\)개의 배열을 만들어 정의할 수 있습니다: \(dp[i][j]:\) \(i\)번째부터 \(j\)번째까지의 점으로 길을 만들 때, 길의 거리의 합의 최솟값. \(hgt[i][j]:\) \(i\)번째부터 \(j\)번째까지의 점으로 길을 만들 때, 높이가 가장 높은 길의 높이(..

문제 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 알고리즘 DP 풀이 점화식을 세우는 것이 조금 어려웠습니다. 하지만 점화식만 잘 세우면 구현과 역추적은 쉽습니다. 배열 \(2\)개를 만들어 다음과 같이 정의합니다; \(dp[i][j]:\) 두 경찰차가 마지막으로 처리한 사건이 각각 \(i, j\)일 때(두 경찰차의 위치가 각각 사건 \(i\), 사건 \(j\)의 위치일 때), 마지막으로 처리된 사건의 다음 사건부터 마지막 사..