BOJ 6171 땅따먹기 (볼록껍질 최적화)

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

6171번: 땅따먹기

볼록껍질 최적화가 일감 이었으나 쉽게 점화식을 유도하지는 못했다.

우선 두 개의 땅 a, b에 대해서 W_a >= W_b 이고 H_a >= H_b 이면, 땅 b는 땅 a와 한 묶음으로 사는게 무조건 이득이다(추가 비용이 발생하지 않는다). 전처리를 해서 b와 같은 땅을 모두 걸러낸 뒤, 너비에 대해서 오름차순으로 정렬을 하면 높이는 내림차순으로 정렬이 된다.

너비에 대해 정렬이된 세 개의 땅 a, b, c를 생각해보자. 이때 (a, c)를 한 묶음으로 사고, (b)를 별도의 묶음으로 사는 것이 최적이 될 것 같지 않은 강한 느낌이 있다. (a, b, c)로 사거나, (a, b), (c) 혹은 (a), (b, c)로 사는 것, 혹은 그냥 (a), (b), (c) 중에 최적이 있을 것 같은 느낌적이 느낌이 든다. 네 개의 땅 a, b, c, d에 대해서도 (a, c), (b, d)와 같은 형태가 최적이 될 일은 없을 것 같다. 엄밀한 증명을 하지는 않았지만 증명을 하지 않아도 될 정도로 확신이 든다. 증명도 하려면 가능할 듯.

위의 느낌적인 느낌이 맞다면 최적해는 항상 너비에 대해 정렬된 땅을 연속된 묶음으로 사는 방법중에 있다.

너비 순으로 땅을 정렬한 뒤, 번호를 매긴다. i번째 땅은 너비가 i번째로 큰 땅이다.

dp[i]를 i번째 땅까지 구매를 하는 경우 최소의 비용이라고 정의를 하면 아래 점화식을 구할 수 있다.

dp[i] = min (j < i) { dp[j] + h[j+1]w[i] }

시간복잡도가 O(n^2)이므로 그냥은 되지가 않는다.

dp 점화식이 아래와 같은 꼴일 때, 볼록껍질 최적화 기법을 사용할 수 있다.

dp[i] = min (j < i) { a[i]b[j] + c[j] } + d[i]

b[j]가 단조 감소 할때 시간복잡도 = O(n log n)

w[i]를 a[i], h[j+1]을 b[j], 그리고 dp[j]를 c[j]에 각각 대입하면, 이 문제의 dp식에 볼록껍질 최적화를 적용할 수 있음을 알 수 있다.

w[i]는 단조증가하고, h[j+1]는 단조감소하므로 O(n)에 dp를 풀 수 있다.

 

볼록껍질 최적화(Convex Hull Trick, CHT) 참고자료:

https://codeforces.com/blog/entry/63823

[Tutorial] Convex Hull Trick — Geometry being useful - Codeforces