컴공과컴맹효묘의블로그

https://www.acmicpc.net/problem/11066 이 문제를 봤을 때 Priorty Queue로 풀 수 있을 줄 알았다. 하지만 제약 조건에서 "연속이 되도록 파일을 합쳐나가고, ..."라는 인접 제약조건이 있기 때문에 인접 조건을 무시하는 Priorty Queue로 풀 수 없었다. DP문제라는 사실을 알아도 풀지 못해 정답을 찾아봐도 처음엔 이해하기 어려웠다... 풀이DP[i][j]를 파일 i번부터 j번까지 합쳤을때 최소비용 이라고 정의하자. 이러면 DP[1][N]이 정답이다.그리고 SUM[i][j]는 파일 i번부터 j번까지 파일을 합친 크기라 정의하자. 그러면 다음과 같은 수식을 구할 수 있다.DP[i][j] = min(DP[i][m] + DP[m+1][j] + SUM[i][m] +..