https://www.acmicpc.net/problem/2647 2647번: 검은점과 하얀점 연결 2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점이다. 하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다. 한 쌍의 점 www.acmicpc.net 처음에 그리디로 한 네 번쯤 삽질하다가 다 예제에 막히고 포기했습니다. 태그 까고 나서 DP인걸 알고도 하루 종일 고민했는데 안 풀려서 cologne 님께 풀이를 들었습니다. $dp[l][r]$을 $l$부터 $r$까지의 구간에서 매칭했을 때의 최솟값으로 두면 됩니다. 역추적도 필요한데, 메모이제이션을 할 때 $l$이 어느 점과 이어졌는지를 기록하면 역추적을 할 수 있..