BOJ 11858

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

 

코드

http://boj.kr/413f27bd03ab448dbbdcb68f18d91605

 

International Zhautykov Olympiad 2014 E

 

난이도 : P1

 

Elapse Time : 실패

 

문제를 보고 $O(N^2K)$ 풀이를 떠올리는 것은 어렵지 않았다. $O(N^2K)$ 풀이는 전형적인 dp 문제였는데 $dp[i][j]$를 $a_1, \cdots, a_j$까지 $i$개의 그룹으로 나누었을 때 가능한 값의 최솟값이라고 정의하면 $dp[i][j]=\underset{k<j}{\mathrm{min}}(dp[i-1][k]+\underset{k+1\leq x\leq i}{\mathrm{max}}A_x)$가 되기 때문에 답을 구할 수 있다. 그러나 $N$의 제한이 $10^5$이기 때문에 최적화를 하여 시간복잡도를 줄일 필요가 있었다. 이를 최적화하는 방법으로 세그먼트 트리를 활용할 생각을 해보았는데 도저히 방법이 떠오르지 않았고 풀지 못했다.

 

sharaelong님에게 monotone stack을 활용하라는 힌트를 받았고 이를 어떻게 활용할지를 생각해 보았다. dp 식에서 $\underset{k+1\leq x\leq i}{\mathrm{max}}A_x$ 부분을 monotone stack을 만드는 데 활용할 수 있겠다는 생각을 했다. $\underset{k+1\leq x\leq i}{\mathrm{max}}A_x=p$인 범위를 $[l,r]$이라 했을 때 스택에 $(p,\underset{l\leq x\leq r}{\mathrm{min}}dp[i-1][x])$를 저장해 놓으면 답을 구할 수 있겠다는 생각을 했다. $[l,r]$에서의 최솟값은 $p+\underset{l\leq j\leq r}{\mathrm{min}}dp[i-1][j]$이지만 우리가 구해야 하는 것은 모든 범위에서 최솟값이므로 세 번째 요소에 누적 최솟값을 넣어 해결하였다.