Informatica Online Judge

  반지 만들기 [1187 / 04A3]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 68   Total Tried : 835


The Champion of this Problem (C++) : gs18085 - ms / 425byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

경곽이는 n개의 반지가 있다. 이 반지들은 모두 금속으로 이루어져 있기 때문에 모두 녹여서 하나의 큰 반지를 만들 수 있다.

그러나 화로의 성능이 좋지 않아 한 번에 2개의 반지만 넣어서 1개의 반지로 만들 수 있다. 만약 3개의 반지가 있다면 먼저 임의의 두 반지를 녹여서 하나로 만든 후, 새로 만들어진 금속덩어리와 나머지 반지를 녹여 하나의 금속덩어리로 만들어야 한다.

금속이나 반지를 화로에 넣어서 녹일 때에는 비용이 든다. 비용은 두 금속 혹은 반지의 무게의 합으로 결정된다. 즉 무게가 a인 금속과 무게가 b인 금속을 화로에 넣어서 하나의 금속으로 만들기 위해서는 a+b만큼의 비용이 든다. 물론 이 때 만들어지는 새로운 금속의 무게 또한 a+b이다.

n개의 반지의 무게가 주어질 때, 이 모든 반지를 녹여서 하나의 금속 덩어리로 만드는 데 드는 최소 비용을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 반지의 수를 나타내는 정수 n이 입력된다.
두 번째 줄에는 각 반지의 무게를 나타내는 수 n개가 공백으로 구분되어 입력된다.
각 반지의 무게는 100,000,000을 초과하지는 않는다.

[Sub-task Info]
#1 : n <= 10 (20%)
#2 : n <= 1,000 (30%)
#3 : n <= 100,000 (50%)

Output

반지를 만드는데 드는 최소비용을 출력한다.

IO Example

입력
3
1 2 3

출력
9

* 설명 : 먼저 무게 1과 2인 반지를 녹여 3인 금속덩어리를 만들고, 무게가 3인 금속덩어리와 3인 반지를 녹여 무게가 6인 금속덩어리를 만든다. 이 때 처음 1+2의 비용과 나중에 3+3의 비용이 들게 되므로 모두 9의 비용으로 만들 수 있다. 이 보다 더 적은 비용으로 만들 수 있는 방법은 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]