모두더하기 > 문제은행



알고리즘 자료구조2

1190 : 모두더하기

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 174 회    시도횟수: 447 회   



이번 문제에서 당신은 주어진 N개의 수를 모두 더하면 된다. 

그런데 그러면 너무 쉽기 때문에, 좀 어려운 부분을 생각해 보자. 

이제 두 수를 더하기 위해서는 두 수의 합에 해당하는 '비용' 이 든다고 생각하자. 

 

1, 2, 3 세 개의 수를 더하는 방법을 살펴 보자.

 

* 한 가지 방법은 (1+2)+3 = (3 + 3) = 6 으로 계산할 수 있고, 

  이때 비용은 (1+2)에서 3의 비용이 (3+3)에서 6의 비용이 들어 총 3 + 6 = 9의 비용이 든다.

* 다른 한 가지 방법은 (1+3)+2 = ( 4 + 2 ) = 6 로 계산할 수도 있고,

  이때 비용은 (1+3)에서 4의 비용이 (4+2)에서 6의 비용이 들어 총 4 + 6 = 10의 비용이 든다.​

* 또 다른 한 가지 방법은 (2+3)+1 = (5+1) = 6로 계산할 수 있고,

  이때 비용은 (2+3)에서 5의 비용이 (5+1)에서 6의 비용이 들어 총 5 + 6 = 11의 비용이 든다.​

 

N개의 수를 입력받아 필요한 최소 비용을 계산하는 프로그램을 작성하라.




첫 줄에 숫자의 개수 N (2≤N≤5,000)가 주어진다. 그 후 한 줄에 N개의 자연수가 주어진다. 이 자연수들은 100,000 이하이다.




한 줄에 필요한 최소 비용을 출력한다.



3
1 2 3
9


5
1 2 3 4 5
33


6
3 6 4 8 9 7
94


7
1 1 4 2 8 8 8
78



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.