[python/파이썬] 백준 16208 귀찮음

문제

현우는 무슨 이유에선지 길이 a1, ..., an의, 총 n개의 쇠막대가 필요해졌다. 하지만 그가 가진 것은 길이 a1+...+an의 하나의 쇠막대뿐이었다. 현우는 이 막대를 직접 잘라서 원래 필요하던 n개의 쇠막대를 만들 것이다. 길이 x+y인 막대를 길이 x, y인 두 개의 막대로 자를 때에는 만들려 하는 두 막대의 길이의 곱인 xy의 비용이 든다. 현우는 최소의 비용으로 이 쇠막대를 잘라서 a1, ..., an의 n개의 쇠막대를 얻고 싶다.

그런데 현우는 이 비용이 얼마나 들지 잘 모르겠다. 그래서 여러분이 막대를 자르는 최소 비용을 계산하는 프로그램을 작성해주면 코드잼 경시대회 점수를 30점 올려주겠다고 제안했다. 어떤가?

입력

첫째 줄에는 현우가 원하는 쇠막대의 수를 나타내는 정수 n이 주어진다. (1 ≤ n ≤ 500,000)

둘째 줄에는 현우가 원하는 쇠막대의 길이를 나타내는 정수 a1, ..., an이 주어진다. (1 ≤ ai ≤ 101)

출력

현우가 필요한 n개의 쇠막대를 얻는 최소의 비용을 출력한다.

서브태스크 1 (4점)

n = 4를 만족한다.

서브태스크 2 (14점)

1 ≤ n ≤ 5,000을 만족한다.

서브태스크 3 (12점)

문제에 제시된 조건 외의 다른 제약은 없다.

예제 입력 1 복사

4
3 5 4 2

예제 출력 1 복사

71

예제 입력 2 복사

10
12 43 22 51 2 55 8 21 98 50

예제 출력 2 복사

55164

 

 

[소스 코드]

 

자르는 비용은 잘린 두 개의 막대의 길이의 곱이다.

비용을 줄이기 위해서는 최대한 짧게 잘라야 한다.

 

예를 들어 길이가 14인 막대가 있을 때

1 13 -> 13

2 12 -> 24

3 11 -> 33

4 10 -> 40

이렇게 두 막대 사이의 길이 차가 줄어들수록 곱은 증가함을 볼 수 있다.

 

따라서 자르고자 하는 막대의 길이들을 오름차순으로 정렬한 후에 자르도록 해야 한다.

n = int(input())

length = list(map(int, input().split()))

total = 0
for i in range(n):
    total += length[i]

length.sort()

next = total
cost = 0
for i in range(n-1):
    next -= length[i]
    cost += (next*length[i])

print(cost)