문제

풀이

첫 시도

n = int(input())

arr = sorted([int(input()) for _ in range(n)])

temp = []

if len(arr) == 1:
    print(arr[0])
    quit()
elif len(arr) == 2:
    print(arr[0] + arr[2])
    quit()
    
else:
    temp.append(arr[0]+arr[1])
    for i in range(2, len(arr)):
        temp.append(arr[i]+temp[i-2])
print(sum(temp))

누적 합 형식으로
배열을 정렬한 후 앞의 결과와 다음 요소의 합을 더하며 선형적으로 진행하였다.

하지만 첫번째 조건문 부터 틀린게
길이가 1이면 비교할 대상이 없어 해당 요소를 출력하는게 아니라 0을 출력해야 한다. (비교할 대상이 없기 때문)

else 문에선 차례대로 계산을 했더니
20, 20, 30, 30인 배열에선
1) 20 + 20
2 ) 40 + 30
을 했더니
40 + 30 > 30 + 30 보다 커 최소 횟수 조건에 만족을 하지 못했다.

두번째 시도

from collections import deque
import sys
n = int(input())

arr = deque([int(sys.stdin.readline()) for _ in range(n)])

add = deque()

if len(arr) == 1:
    print(0)
    quit()
elif len(arr) == 2:
    print(arr[0] + arr[2])
    quit()
    
else:
    for i in range(n-1):
        temp = 0
        a = min(arr)
        arr.remove(a)
        
        b = min(arr)
        arr.remove(b)
        
        temp = a + b
        add.append(temp)
        arr.append(temp)
print(sum(add))

deque를 이용해 피연산자가 된 요소들은 pop를 해주고, 연산 결과는 append를 해주고 해당 배열을 매번 정렬해주며 진행했다.

하지만 이 결과 시간초과가 떴다.
정렬 알고리즘의 시간 복잡도는 O(nlogn)으로 비교적 낮지만
input size가 100,000이라 매번 정렬을 진행하면 2초안에 끝날수가 없었다.

최종 풀이

import heapq

n = int(input())
arr = [int(input()) for _ in range(n)]
ret = []

if len(arr) == 1:
    print(0)
    quit()
elif len(arr) == 2:
    print(arr[0] + arr[1])
    quit()
    
else:
    heapq.heapify(arr)
    for i in range(n-1):
        a = heapq.heappop(arr)
        b = heapq.heappop(arr)
        temp = a+b
        heapq.heappush(arr, temp)
        ret.append(temp)
    print(sum(ret))

덱이 아닌 heap 자료구조를 사용했다.
파이썬 heap 모듈은 min heap를 사용한다.
heap는 정렬을 할 필요가 없기 때문에 deque, list 보다 이 문제를 빠르게 해결 할 수 있다.

마찬가지로 2개의 요소를 pop 해 더한 값을 다시 heap 에 넣어주고, 더한 값을 또 ret 배열에 넣어 주는 것을 마지막 1개가 남을 때 까지 반복해준다.

heap 자료구조에 자세한 설명은 아래 링크를 통해 확인하면 된다.