스키장 만들기(skiresort) > 문제은행

본문 바로가기


실전대비 Level5

1481 : 스키장 만들기(skiresort)

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 16 회    시도횟수: 106 회   



평창 동계올림픽을 잘 치루기 위해 스키장을 만들기 위한 장소를 물색하다가 교통도 편리하고 크기도 적당한 길게 이어진 땅을 확보하였다. 그런데 그 땅은 현재 너무 울퉁불퉁해서 스키장을 만들기 위해서는 우선 높이가 차례대로 단조증가하거나 단조감소하도록 기초작업을 해야 한다. (단조증가란 감소하는 부분이 없이 꾸준히 증가하는 것이고 단조감소란 증가하는 부분이 없이 꾸준히 감소하는 것을 말한다. 즉, 높이가 같은 것은 상관이 없다.) 이러한 작업을 위해 땅을 일정하게 N개의 부분으로 나누고 각 부분의 높이를 구했다.

 

한 부분의 높이를 조정하는 데에는, 높이거나 낮추기 위해 조정하는 높이만큼의 비용이 든다. 이 땅을 단조증가하거나 단조감소하게 만들기 위해 필요한 최소비용을 구하는 프로그램을 작성하시오.


첫줄에 땅을 나눈 부분의 수 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째줄부터 나누어진 각 부분의의 높이 Hi (1 ≤ Hi ≤ 1,000,000,000)가 주어진다.


첫줄에 길을 고르게 하는 데 드는 비용을 출력한다. 결과값은 231-1 이하의 값이다.

[Copy]
7
1
3
2
4
5
3
9
[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.