구간 나누기 - KOITP_201601_INTERVALDIVISION

문제 링크(koitp.org/problem/KOITP_201601_INTERVALDIVISION/)

동적계획법으로 해결할 수 있다.

dp(k, i) : i번째 수까지 k개의 구간을 정했을 때의 최적해

dp(k, i) = max[dp(k-1, j) + max(A(j+1)~A(i)) - min(A(j+1)-A(i))]

여기서 max( )와 min( )을 계산하는데 O(N)이 걸려서 한 가지 변형을 한다.

dp_contain_max(k, i) = max[dp(k-1, j) + max(A(j+1)~A(i))]

dp_contain_min(k, i) = max[dp(k-1, j) - min(A(j+1)~A(i))]

그러면 dp(k, i) = max[dp_contain_max(k, i) - A(i), dp_contain_min(k, i) + A(i)]

dp_contain_max와 dp_contain_min은 dp(k, i)에서 i를 증가시키면서 같이 구해나갈 수 있다.

따라서 전체적인 시간복잡도는 O(NK)