[BOJ] 2647번: 검은점과 하얀점

https://www.acmicpc.net/problem/2647

고등부 정올 1번 문제 치고 은근 까다롭네요. D[i][j]를 s[i:j]를 연결할 때의 최솟값, h[i][j]를 s[i:j] 구간을 연결할 때 가장 높이 올라가는 연결선의 높이, conn[i][j]를 s[i:j] 구간을 연결할 때 i가 연결하는 곳이라고 둔 후에, D[i][j]를 구할 때 우선 i와 j-1을 연결하는 경우를 처리한 이후, sep = i+2, i+4, ...에 대해 D[i][sep]+D[sep][j]를 생각하면 됩니다.

값 자체는 쉽게 구해지는데 그 이후에 연결 상태를 복원하는 것이 조금 까다로웠습니다. 저는 conn을 이용해 recursive하게 해결했습니다.

https://github.com/blisstoner/BOJ/blob/master/2647.cpp