하바나바나나

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$이 어느 점과 이어졌는지를 기록하면 역추적을 할 수 있..

https://www.acmicpc.net/problem/1691 1691번: 석판 첫 줄에는 대리석 원판의 크기를 나타내는 W(가로 길이), H(세로 길이)가 들어있다. 다음 줄에는 우리가 원하는 크기의 개수 N이 있고, 그다음 N줄에는 그 크기들이 역시 가로, 세로 순으로 들어있 www.acmicpc.net dp로 풀 수 있는 문제입니다. 석판은 가로나 세로 방향으로 완전히 잘라야 한다는 점을 생각하면, 석판을 자르는 것을 부분문제로 나눠서 생각할 수 있습니다. 왼쪽 위를 원하는 모양의 석판 중 하나로 채워주면 두 가지 경우가 생깁니다. 가로로 먼저 자르고 세로로 자르는 것과 세로로 먼저 자르고 가로로 자르는 것입니다. 각 경우마다 새로 생기는 석판은 두 개가 되고 해당 석판을 다시 자르는 것으로 생..

https://www.acmicpc.net/problem/5502 5502번: 팰린드롬 팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 www.acmicpc.net 딱 보고 아 이거 이차원 dp네 라고 생각했는데 그 이후로 한 이틀간 못 풀었습니다... 은둔고수 님이 저에게 완성된 팰린드롬에서 뺀다고 생각해 보라고 힌트를 주셨는데, 그거 듣고 조금 고민하다가 풀었습니다. $dp(i, j)$는 $i$번째 문자와 $j$번째 문자가 같으면 $dp(i+1,j-1)$이고 다르면 $min(dp(i+1, j), dp(i, j-1)) + 1$이 됩니다. cologne 님이 처음에 원래 문자..