USACO 2008 Mar Gold 1- 토지 구입(Land Acquisition) > 문제은행 : 정보올림피아드&알고리즘




1878 : 토지 구입(Land Acquisition)

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
4 회   
시도횟수
21 회   

문제

농부 창호는 지금 자신의 눈앞에 펼쳐진 N(1≤N≤50,000)개의 땅을 사고자 한다.

각각의 땅은 사각형의 모양새를 띄고 있고, 정수 범위의 가로와 세로로 이루어져 있다. 가로와 세로는 서로 바뀔 수 없다.

농부 창호가 한 개의 땅을 사게 되면, (가로)×(세로)만큼의 비용을 지불해야 하는데, 

한 번에 여러 개의 땅을 사게 되면 (땅들의 가로 중 최댓값)×(땅들의 세로 중 최댓값)만큼의 비용을 지불하면 된다. 

 

예를 들어 창호가 15×15의 땅과, 5×20의 땅을 샀을 경우엔 각각 225, 100의 비용이 필요하기 때문에 총 325의 비용을 지불하는데, 

15×15의 땅과 5×20의 땅을 한 번에 살 경우 15×20=300의 비용만을 지불 하면 된다.

 

창호는 모든 땅을 사고자 하는데, 한 번에 모든 땅을 사는 것이 아닌, 여러 번에 걸쳐 땅을 사려고 한다. 

이 때 창호가 지불해야 하는 비용을 최소화 하는 프로그램을 작성하라.


입력형식

첫 번째 줄에는 창호가 살 수 있는 땅의 개수 N(1≤N≤50,000)이 입력된다.
그 다음 줄부터는 N개의 땅의 가로와 세로가 공백을 사이에 두고 한 줄에 하나씩 입력된다. 

가로와 세로의 범위는 1이상 1,000,000이하이다.


출력형식

창호가 모든 땅을 살 때 내게 되는 최소의 비용을 출력한다.


입력 예

4
100 1
15 15
20 5
1 100

출력 예

500

Hint!

다음과 같이 땅을 사게 되면 창호는 최소의 비용을 지불하게 된다. 

한번은 100×1의 땅을 사서 100의 비용을 지불하고, 1×100의 땅을 사서 100의 비용을 추가로 지불하고, 

마지막에 15×15의 땅과 20×5의 땅을 한 번에 사서 총 300의 비용을 지불하면 500의 비용을 지불한다. 

이는 가능한 모든 경우 중 최솟값이며, 구입 순서는 상관없다




DP, convex hull trick

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP