Problems
주어진 집합 A[]의 N개의 수를 다음 규칙에 따라 더하는 문제를 생각해보자.
더하는 규칙은 다음과 같다.
1. 집합 A[]에서 두 개의 수를 뽑아 더한 결과값 ret를 구한다.
2. 비용의 합 sum에 ret를 더하고, ret를 A[]에 넣는다.
3. 집합 A[]의 원소가 1개 남을 때까지 1, 2번 작업을 반복한다.
예를 들어 N = 5 이고 A[] = {1, 2, 3, 4, 5}가 주어진 경우를 살펴보자.
여러 가지 방법 중에 2가지만 살펴보면 다음과 같다.
[방법 1]
* A[] = {1, 2, 3, 4, 5}, sum = 0
* A[] = {3(1+2), 3, 4, 5}, sum = 3
* A[] = {6(3+3), 4, 5}, sum = 3 + 6 = 9
* A[] = {10(6+4), 5}, sum = 9 + 10 = 19
* A[] = {15(10+5)}, sum = 19 + 15 = 34
[방법 2]
* A[] = {1, 2, 3, 4, 5}, sum = 0
* A[] = {3(1+2), 3, 4, 5}, sum = 3
* A[] = {6(3+3), 4, 5}, sum = 3 + 6 = 9
* A[] = {6, 9(4+5)}, sum = 9 + 9 = 18
* A[] = {15(6 + 9)}, sum = 18 + 15 = 33
다른 방법을 사용하여도 [방법 2]의 경우보다 비용을 더 줄일 수는 없다.
따라서 위 예의 경우 비용의 합의 최솟값은 33이다.
위 규칙과 같이 수행할 때 비용의 합 sum이 최소가 되는 경우를 구하여
출력하는 프로그램을 작성하시오.
Input
첫 줄에 숫자의 개수 N (2≤N≤5,000)가 주어진다.
그 후 한 줄에 N개의 자연수가 주어진다. 이 자연수들은 100,000 이하이다.
Output
한 줄에 필요한 최소 비용을 출력한다.
Example #1
3
1 2 3
9
Example #2
5
1 2 3 4 5
33
Example #3
6
3 6 4 8 9 7
94
Example #4
7
1 1 4 2 8 8 8
78
You must sign in to write code.