2304 창고 다각형

기둥을 오복한 부분을 만들지 않고 전체를 덮을 때 사용되는 최소의 면적을 구하는 문제이다.

오목한 부분을 만들지 않는다는것은, 감소하다가 증가하는 일 없이, 쭉 감소하거나 쭉 증가하는것을 의미한다. 따라서 가장 높은기둥을 찾고, 그 기둥을 중심으로 왼쪽으로 감소, 오른쪽으로 감소 시키면서 면적을 구하면 된다.

다음 기둥을 고르는 방법은 끝부터 현재기둥 중에 현재기둥 다음으로 가장 높은 기둥을 찾으면 된다.

소스