USACO 2009 March Competition- 원금상환 > 문제은행 : 정보올림피아드&알고리즘




1593 : 원금상환

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
12 회   
시도횟수
22 회   

문제

"돈을 빌려주지도, 빌리지도 말자", 라는 조언을 철기가 명심했다면 지금과 같은 고생을 하지 않아도 되었을 것이다. 

그러나! 철기는 N(1≤N≤100,000)명의 친구에게 돈을 빌리거나 빌려주었다.

 


편의상 친구들은 1번부터 N번까지 번호를 붙여서 부르기로 하자.


원금회수의 날이 마침내 다가왔다. 참고로 철기는 자신이 남들에게 빌린 돈보다 빌려준 돈이 많다. 

철기의 친구들의 집은 모두 1차원 X좌표 상에 있다. 

철기 집의 위치의 좌표는 0이며, i번 친구의 좌표는 i다. 

철기는 자신의 집에서 출발하여 친구의 집을 돌아다니면서 빌려준 돈은 받고, 빌린 돈은 갚으려고 한다.

 


철기는 X좌표 상에서 왼쪽 오른쪽으로만 움직일 수 있다. 

다시 말해서 i좌표에 있으면 i+1, i+2, i+3, ... 혹은 i-1, i-2, i-3 같은 순으로만 움직일 수 있다는 것이다.


우선 철기는 자신의 집에서 출발하여 1번부터 N번의 순서로 친구의 집을 방문하며, 돈을 갚거나 돈을 받는다. 

i번 친구는 철기에게 Di 의 돈을 빌렸다(-1,000 ≤ Di ≤ 1,000; Di != 0). 만약 Di가 0보다 작을 경우, 철기가 |Di| 만큼의 돈을 빌렸다는 것이다. 

처음에 철기는 0에서 움직이기 시작하는데, 초기에 가지고 있는 돈은 0이다. 

만약 철기에게 돈을 갚아야 할 친구의 집에 도착하게 되면 Di만큼의 돈이 생기게 된다. 

돈을 빌린 친구의 집에 다다랐을 경우, 가지고 있는 돈이 |Di|보다 크거나 같을 경우에만 돈을 갚을 수 있다.


자신의 집에서 출발하여 친구에게 빌려준 돈과 빌린 돈을 다 처리하고, 

N번째 친구의 집에 놀러갈 때 철기가 이동하게 되는 최소의 거리를 찾는 프로그램을 작성하라.


입력형식

입력의 첫 번째 줄에는 N이 들어오며 그 다음 줄부터 순서대로 Di가 입력된다.

출력형식

철기가 이동하게 되는 최소의 거리를 출력한다.

입력 예

5  
100 
-200 
250 
-200 
200

출력 예

9

Hint!




greedy

경기도 안양시 동안구 평촌대로 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