소시지 공장 > 문제은행

본문 바로가기


알고리즘 그리디

1669 : 소시지 공장

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 1113 회    시도횟수: 5120 회   



영훈이가 소시지 공장에 견학을 갔다. 그 소시지공장에서는 하나의 기계가 길이와 너비가 다양한 소시지를 만들어 내고 있었다.

 

유심히 살펴보니 그 기계는 현재 만들고 있는 소시지의 길이와 너비가 바로 전에 만들었던 소시지의 길이, 너비보다 크거나 같아야만 기계가 쉬지 않고 작동하고 있었다. 만약 현재 만들고 있는 소시지의 길이 또는 너비가 바로 전에 만든 것보다 작다면, 기계가 준비 작업을 하는데 1분이 소요된다는 것을 알았다.

 

영훈이는 주문 받은 소시지의 길이와 너비를 보고 어떤 소시지부터 만들어 나가는 것이 기계의 준비 작업에 소요되는 시간을 줄일 수 있을지 고민하고 있다.

 

주문받은 소시지들을 만드는데 기계가 준비 작업에 소요한 최소의 시간을 구하는 프로그램을 작성하시오.

 

단, 첫 소시지를 만들 때는 기계의 준비작업 시간이 1분 소요된다.


첫 줄에는 주문받은 소시지의 개수 N(1≤N≤5,000)이다. 둘째 줄에는 소시지의 길이 SL과 소시지의 너비 SW가 N개의 쌍으로 나열된다.



주문받은 소시지들을 만드는데 기계가 준비 작업에 소요한 최소의 시간을 출력한다.


[Copy]
5 
4 9 5 2 2 1 3 5 1 4
[Copy]
2


[Copy]
3
1 3 2 2 3 1
[Copy]
3





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.