볼록껍질최적화 썸네일형 리스트형 BOJ 6171 땅따먹기 (볼록껍질 최적화) https://www.acmicpc.net/problem/6171 6171번: 땅따먹기 (1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다. www.acmicpc.net 볼록껍질 최적화가 일감 이었으나 쉽게 점화식을 유도하지는 못했다. 우선 두 개의 땅 a, b에 대해서 W_a >= W_b 이고 H_a >= H_b 이면, 땅 b는 땅 a와 한 묶음으로 사는게 무조건 이득이다(추가 비용이 발생하지 않는다). 전처리를 해서 b와 같은 땅을 모두 걸러낸 뒤, 너비에 대해서 오름차순으로 정렬을 하면 높이는 내림차순으로 정렬이 된다. 너비에 대해 정렬이된 세 개의 땅 a, b, c를 생각해보자. 이때 (a, c.. 더보기 이전 1 다음