Time Limit: 1s
Memory Limit: 128MB
WithCS 농장 아저씨는 목장 주변의 울타리를 수리하려고 합니다. 아저씨는 울타리를 꼼꼼히 살펴봐서 Li(1 ~ 5000)의 길이를 갖는 N(1 ~ 20000)개의 나무 판자가 필요하다는 것을 알게 되었습니다. 그리고선 N개의 나무 판자를 얻기에 딱 맞는 길이의 나무 판자 하나를 구매하였습니다. WithCS 농장 아저씨는 톱질로 발생하는 톱밥로 인한 길이의 손실은 고려하지 않는다고 합니다.
그런데 WithCS 아저씨는 슬프게도 나무판자를 자를 톱이 없다는 사실을 깨닫고 말았습니다. 그래서 옆 Math 농장 아저씨한테 톱을 빌릴 수 있을지 정중히 물어보았습니다.
Math 농장 아저씨는 WithCS 농장 아저씨에게 톱을 빌려주지 않고 나무판자를 한번 자를 때마다 돈을 받기로 했습니다. 비용은 자르는 나무판자의 길이만큼 발생합니다. 예를 들어 21의 길이를 가지는 나무판자를 자를 경우 21원을 내야 합니다.
Math 농장 아저씨는 WithCS 농장 아저씨에게 나무판자를 자르는 순서와 위치를 결정할 수 있게 하였습니다. WithCS 농장 아저씨를 도우기 위해 최소의 비용으로 N개의 나무판자를 만드는 방법을 알아봅시다. 자르는 순서에 따라 중간에 나오는 나무목재의 길이가 서로 다르기 때문에 비용이 다르게 산정됩니다.
* Line 1 : 단일 정수 N (필요한 나무판자의 수)
* Line 2 ~ N+1 : 단일 정수 Di (필요한 나무판자의 길이)
* Line 1 : N-1개의 자르는 과정에서 발생하는 비용의 최소값
3 8 5 8
34
8,5,8의 길이를 갖는 3개의 나무 목재가 필요합니다. 처음에는 8+5+8 = 21의 길이를 가지는 나무판자로 시작합니다. 첫번째 자르는 비용은 21이 발생하며, 그 결과로 8, 13의 길이를 가지는 나무판자로 나뉩니다. 두번째는 13의 비용으로 5,8의 길이를 가지는 나무판자로 나뉩니다. 즉, 21 + 13 = 34의 비용이 발생합니다.
처음에 5와 16의 길이를 가지는 나무판자로 나눌경우 발생 비용은 21 + 16 = 37의 비용이 발생됩니다. 이는 34보다 큰 값이므로 정답이 아닙니다.