슬라임 합치기

출처 : 백준 #14241

시간 제한	메모리 제한
2초	512 MB

---

문제

영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.

모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.

영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다.
둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다.

---

출력

첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다.

---

입출력 예시

예제 입력 1

2
3 4

예제 출력 1

12

---

예제 입력 2

3
2 2 2

예제 출력 2

12

---

예제 입력 3

3
1 2 3

예제 출력 3

11

---

예제 입력 4

3
3 1 2

예제 출력 4

11

---

풀이

풀이 설명

• 슬라임의 크기를 두 개씩 뽑아서 곱한 값을 점수에 추가하고 더한 값은 다시 배열에 집어 넣어 똑같은 과정을 반복한다.

python code

# 백준 14241번
from sys import stdin
from collections import deque

def slime(n, slimes):
    slimes.sort(reverse=True)   # 큰 순서대로 정렬하기

    deq = deque()
    for i in range(n):
        deq.append(slimes[i])

    result = 0  # 얻는 점수

    while (len(deq) > 1):
        x = deq.popleft()
        y = deq.popleft()
        result += x*y   # 곱한 만큼 점수로 추가
        deq.appendleft(x+y) # 합친 슬라임은 다시 deq에 집어넣기

    return result   # 점수 반환

n = int(stdin.readline())
slimes = list(map(int, stdin.readline().split()))

result = slime(n, slimes)
print(result)