메뉴 건너뛰기

문제

00b33 세차장 3  

시간메모리제출 올바른 답 비율
1초64MB
70
33
47.1%


나의 횟수나의 최근 판정시도 성공 비율
2624
92.3%
세차장 

맨체스터에 살고 있는 세차장 주인인 마돈나는 고민이 많다. 전날 세차장을 이용하겠다고 예약한 손님들이 대기시간이 많다고 불평하기 때문이다. 결국 예약을 했음에도 기다리는 시간이 많아지는 현상이 발생하게 되었다.

여러분은 마돈나를 도와서 어려움에 빠진 세차장을 어떻게 운영해야 하는지 알려줘야 한다. 지금 이 세차장 앞에 N대의 차들이 줄을 서있다. 차들은 1번부터 N번까지 번호가 매겨져 있으며, i번 차는 세차를 하는데 걸리는 시간은 Pi분이다. 차들이 줄을 서는 순서에 따라서, 세차를 하는데 필요한 시간의 합이 달라지게 된다.

예를 들어, 총 5대가 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 차는 3분만에 세차 할 수 있다. 2번 차는 1번 차가 세차할때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 차는 1번, 2번 차가 세차할 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 차는 3+1+4+3 = 11분, 5번 차는 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 차들이 세차하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다. 줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 차는 1분만에, 5번 차는 1+2 = 3분, 1번 차는 1+2+3 = 6분, 4번 차는 1+2+3+3 = 9분, 3번 차는 1+2+3+3+4 = 13분이 걸리게 된다. 각 차는 세차하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다.

이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다. 줄을 서 있는 차의 수 N과 각 차가 세차하는데 걸리는 시간 Pi가 주어졌을 때, 각 차가 세차하는데 필요한 시간의 합의 최소값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 차가 세차하는데 필요한 시간의 합의 최소값을 출력한다.

예시
1입력
5
3 1 4 3 2
출력
32
위로