🔥

문제

윌리의 직박구리 폴더에는 N개의 파일이 있다. 윌리는 이 파일들을 전부 합쳐 하나의 파일로 만드려고 한다. 파일을 합칠 때에는 두 파일을 하나로 합치는 것을 반복해야 한다. 합칠 때에는 두 파일의 크기를 더한 것만큼의 시간이 걸린다.


놀랍게도, 파일을 고르는 순서에 따라서 걸리는 시간이 달라진다. 예를 들어 크기가 10, 20, 40인 파일이 있다면 10과 20을 합친 뒤, 합친 30과 40을 합친다면 (10 + 20) + (30 + 40) = 100의 시간이 필요하다. 그러나 10과 40을 합친 뒤, 합친 50과 20을 합친다면 (10 + 40) + (50 + 20) = 120의 시간이 필요하므로 덜 효율적인 방법이다.


N개의 파일 크기가 주어질 때, 필요한 시간의 최솟값을 구해보자.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)


다음 N개의 줄에 걸쳐 파일의 크기가 주어진다. 이는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 시간을 출력한다.

예제 1 입력

3
10
20
40

예제 1 출력

100

Source

from queue import PriorityQueue

pq = PriorityQueue()
n = int(input())
for i in range(n):
    pq.put(int(input()))

total = 0

for i in range(1, n):
    x = pq.get() + pq.get()

    total += x
    pq.put(x)

print(total)

참고