[BOJ] 14177번: 티떱랜드

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

$D_{t,n}$ 를 n명을 t개의 열차에 태웠을 때 최소 어색함의 합이라고 할 때 $D_{t,k} = \min_{j < k} D_{t-1,j}+val(j+1,j+2,...,k)$입니다. 해당 value는 적절한 DP를 통해 $O(N^2)$의 선행 계산으로 전부 구해둘 수 있습니다. 이후 Divide and Conquer Optimization을 이용해 시간복잡도를 $O(KNlgN)$으로 떨굴 수 있습니다.

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