짐정리 > 문제은행

본문 바로가기


문제은행

1075 : 짐정리

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



일렬로 놓인 짐칸에는 서로 다른 무게를 갖는 짐이 한 칸에 하나씩 놓여 있다. 가장 앞에 위치한 짐칸에 가장 가벼운 짐이 놓이고 이어 무게 순서대로 짐이 놓여 가장 마지막에 위치한 짐칸에는 가장 무거운 짐이 놓이도록 짐칸을 정리하려 한다. 짐을 옮길 때는 두 짐의 위치를 서로 바꾸어 주어야 하며, 이 때 두 짐의 무게의 합만큼의 힘이 든다.

 

짐칸의 개수와 짐칸에 놓인 짐의 무게가 차례대로 주어질 때 짐칸을 정리하기 위해 필요한 최소 힘을 구하는 프로그램을 작성하시오.

 

예를 들어, 무게가 각각 10, 2, 8, 5인 네 개의 짐이 짐칸에 차례로 놓여 있다고 하자. 무게가 10인 짐과 무게가 2인 짐의 위치를 서로 바꾸어 주고, 이어 무게가 10인 짐과 무게가 5인 짐의 위치를 서로 바꾸어 주면 짐칸 정리를 마치게 된다. 이 때 드는 총 힘은 < 그림 1 >과 같이 (10+2) + (10+5) = 27 이 된다.

 

e3050b66a1b29a01767400d7560a4131_1449735
 

반면 먼저 무게가 2인 짐과 5인 짐의 위치를 서로 바꾸어 주고, 이어 무게가 10인 짐과 2인 짐의 위치를 서로 바꾸어 주어도 짐칸이 정리된다.

 

 e3050b66a1b29a01767400d7560a4131_1449735 

 

이렇게 했을 때 드는 총 힘은 < 그림 2 >와 같이 (2+5) + (10+2) = 19 가 된다.

 

 


첫 째줄에 짐칸의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 짐의 무게가 차례대로 주어진다. 짐칸의 수는 1,000 이하의 자연수이며, 짐의 무게는 10,000 이하의 자연수이다. 모든 짐의 무게는 서로 다르다.


첫째 줄에 짐칸을 정리하기 위해 필요한 최소 힘을 출력한다.

[Copy]
4 
10 
2 
8 
5
[Copy]
19






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.