https://www.acmicpc.net/problem/13974
13974번: 파일 합치기 2
소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본
www.acmicpc.net
dp[i][j] = i번 파일부터 j번 파일까지 합치는데 필요한 최소 비용이라고 정의하고,
s[i][j] = i번 파일부터 j번 파일까지 파일 크기의 합이라 하면, 아래의 dp 점화식을 얻을 수 있다.
dp[i][j] = min(i<=k<=j) { dp[i][k] + dp[k][j] } + s[i][j]
문제는 n=5000인데, 위의 dp는 O(n^3)이라서 타임아웃이 날 것이 뻔하다.
dp가 위와 비슷한 형태일 때, 사용할 수 있는 최적화 기법으로 크누스 최적화라는 것이 있는데, s[i][j]가 아래 조건을 만족하면 사용할 수 있다.
dp[i][j] = min(i<k<j) { dp[i][k] + dp[k][j] } + s[i][j] (i<k<j 임에 주의해야 한다.)
1. s[a][c] + s[b][d] <= s[a][d] + s[b][c]
2. s[b][c] <= s[a][d]
where a<=b<=c<=d
그러면 유효한 k의 범위는 k[i, j-1] <= k[i][j] <= k[i+1][j] 이다.
https://wiki.algo.is/Knuth's%20optimization
AlgoWiki - Knuth's optimization
Applicability Knuth’s optimization applies when the dynamic programming recurrence is approximately of the form \[ \mathrm{dp}[i][j] = \min_{i where \(A[i][j-1] \leq A[i][j] \leq A[i+1][j]\). Here \(A[i][j]\) is the smallest index \(i < k^\star < j\) tha
wiki.algo.is
이 문제의 dp를 위의 조건을 만족하게 아래와 같이 수정하면 크누스 최적화를 적용해 O(n^2)에 풀 수 있다.
dp[i][j] = i번 파일부터 j-1 번 파일까지 합치는데 필요한 최소 비용
s[i][j] = i번 파일부터 j-1번 파일까지 파일 크기의 합
dp[i][j] = min(i<k<j) { dp[i][k] + dp[k][j] } + s[i][j]
'problem solving' 카테고리의 다른 글
| BOJ 13261 탈옥 (분할정복 동적계획법 최적화) (0) | 2022.01.06 |
|---|---|
| BOJ 10350 은행 (IMO 1986) (5) | 2021.12.28 |
| BOJ 8872 빌라봉 (0) | 2021.12.26 |
| BOJ 3683 고양이와 개 (0) | 2021.11.21 |
| Leetcode 1835. Find XOR Sum of All Pairs Bitwise AND (0) | 2021.04.24 |