문제 번호 5104 --팬스고치기(Fence Repair)

5104: 팬스고치기(Fence Repair)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 18  해결 문제 수: 4
[제출][채점상황][게시판][:]

문제 설명

존은 목장 주위의 울타리 부분 부분 교체하기를 원한다. 펜스를 둘러본 후 N (1 ≤ N ≤ 20,000) 개의 나무가 필요하다는 것을 알았다.

각각은 정수 크기 Li ( 1 <= Li <= 50,000) N 개의 나무를 만들 수 있는 긴 나무를 샀다.(즉 Li 의 크기의 합이다) 존은 kerf , 톱질 할 때 나오는 톱밥의 길이는 무시한다.

여러분도 역시 이를 무시해야 한다.

존은 나무를 자를 톱을 가지고 있지 않아서 긴 나무를 들고 농부 돈의 집으로 가서 정중하게 톱을 빌려 줄 수 있는지를 물었다.

그런데 자본주의 물든 돈은 존에게 톱을 빌려주지 않았다. 대신 존에게 N-1 번의 컷 각각의 돈을 받기로 제안했다. 즉 21 크기의 나무를 자를 때는 21 센트의 비용을 준다.

존이 임의 위치에 나무를 자를 수 있는 경우 가장 최소의 비용으로 나무를 자를수 있게 존을 돕는 것이 문제이다.

입력

첫 줄에는 나무 토막의 수 N 이 주어지고 ,

다음 줄 부터 N 줄에는 각각 나무 토막의 길이가 주어진다.

출력

최소 비용을 출력한다.

입력예시

3
8
5
8

출력예시

34

도움말

그는 3 조각 8 , 5 , 8 의 크기의 나무를 얻기를 원한다. 처음 나무의 크기는 8+5+8 = 21 이다.

    첫 번째 컷은 21 의 비용이 들고 , 13 과 8 로 나눈다.

    두 번째 13 의 비용이 든다. 13 을 8 과 5 로 나눈다.

이렇게 하면 34 의 비용이 든다.

만약

    첫 번째 컷은 21 의 비용이 들고 , 16 과 5 로 나눈다.

    두 번째 컷에서 16 의 비용이 들어, 8 과 8 로 나누면

합이 37 이 되는데 이는 34 보다 더 많다.

번역 : dovelet.com

출처

[제출][채점상황]