짐정리 timer 1초 memory 128MB

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

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

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

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

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