BOJ 6171 : 땅따먹기

https://www.acmicpc.net/problem/6171
Naive한 dp로 먼저 생각해보자.

dp[i] = i번째 땅까지 샀을 때의 비용의 최솟값

dp[i] = min(dp[j-1]+max(w[k])*max(h[k])) (0<=j<=i && j<=k<=i)

 

이때 필수적으로 입력으로 정해진 순서를 적용해서 구하라는 말이 없으므로 w[i]에 대한 오름차순 정렬을 해보자.

 

여기서 관찰할 수 있는 게 있는데, 정렬하고 나서의 h[i]<=h[i+1]인 원소가 있으면 (w[i],h[i])는 고려 안해도 된다.

w[i]<=w[i+1] & h[i]<=h[i+1]을 만족하기에 실질적인 비용면에선 (w[i],h[i])가 무시되기 때문이다.

 

그러므로 이런 원소들을 빼주면, w[i]는 단조 증가, h[i]는 단조 감소 상태가 된다.

 

그렇다면 dp식을 좀 더 최적화할 수 있다.

dp[i] = min(dp[j-1]+w[i]*h[j]) (0<=j<=i)

 

그러나 n<=50000이기 때문에 아직 부족하다.

 

 

 

w[i], h[i]가 단조성이 있는 상태이고, 식 자체가 직선꼴로 나타나는 것을 관찰해보자.

 

그렇다면 여기서 CHT(Convex Hull Trick) 최적화를 이용하면 된다.

시복은 O(n).

 

코드