문제

• 
• 시간 제한: 2초
• 메모리 제한: 256MB

Problem Analysis

1~n의 최종 합은, 1 ~ m의 합과 m+1 ~ n의 합과 같다. 무작위의 m 중에서 최소를 만드는 m을 찾으면 된다. Naive 하게 풀면 굉장히 오래 걸리겠지만, 이 문제는 subproblem이 반복되기 때문에 Dynamic Programming으로 풀 수 있다.

Algorithm

• i~j의 최소 비용을 dp[i][j]에, 단순 합을 sum[i][j]에 저장한다.
• Bottom-Up 방식으로, dp[i][j] = min( dp[i][m] + dp[m+1][j] + sum[i][j] ) (i<=m<j) 을 구한다.

Data Structure

• DP, KxK Array
• Sum, KxK Array

결과

Other

시간 복잡도는 O(k^3)이다.