모두더하기 > 문제은행



알고리즘 자료구조2

1190 : 모두더하기

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



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

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

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

 

1,2,3 세 개의 숫자를 더하기 위해서는 이들을 

(1+2)+3 으로 계산할 수도 있고,

(1+3)+2 로 계산할 수도 있고, 

1+(2+3) 으로 계산할 수도 있다.

 

세 방법은 각각 9,10,11 의비용이 든다. 이때 필요한 최소 비용을 계산하는 프로그램을 작성하라.




첫 줄에 숫자의 개수 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



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.