문제
안전한 서울시를 만들겠다는 공약을 내세워 당선된 서울시장은 몇 년 전 산사태가 일어났던 우면동 일대를 시찰하다가 배수로를 지탱하는 철근하나가 여러 조각으로 절단된 것을 발견하였다.
장마철이 돌아오기 전에 조속히 수리를 지시하고 예산을 편성하려고 하였다. 절단된 철근을 완전히 새것으로 교체하면 좋겠지만 그렇게 하려면 배수로 전체를 다시 보수해야 하기 때문에 많은 비용이 든다. 그래서 최소의 비용으로 철근을 튼튼하게 잇는 방법을 고안하였다.
조각난 철근을 이을 때의 비용은 그 조각을 이어서 만들어진 조각의 길이와 같다. 따라서 조각을 이어나가는 순서를 잘 정하면 많은 예산을 절감할 수 있다.
철근을 모두 연결하여 하나의 철근으로 만들기 위해 필요로 하는 최소의 비용을 구하여 출력하는 프로그램을 작성하라.
입력
첫 번째 줄에 절단된 철근의 개수 N(1≤N≤20000)이 입력되고 이후 N개의 줄에 걸쳐 각 철근의 길이를 나타내는 정수 L1 L2 ... LN(1 ≤ Li ≤ 50000)가 입력된다.
출력
철근을 잇기 위해 필요로 하는 최소의 비용을 출력한다.
예제
3
8
5
8
34
힌트
출처
KYIO2014(성결대)
로그인해야 코드를 작성할 수 있어요.