이번 문제는 우선순위큐를 사용하여 우선순위큐의 크기가 1보다 클 동안 가장 작은 두 수를 더한 값을 결과값에 계속해서 더해주어 해결하였다.

가장 작은 두 카드덱을 합치는 것이 가장 작은 결과를 도출한다는 패턴을 쉽게 알 수 있었다.

초기에는 우선순위큐를 사용하지 않고 리스트를 사용하여 while문 안에서 매 반복마다 .sort()함수를 사용해 오름차순 정렬하였는데 이는 while문의 O(n)과 .sort()함수의 O(n)이 곱해져 시간복잡도가 O(n^2)가 나오기 때문에 당연히 시간초과가 발생하였다.

파이썬에서 우선순위큐는 힙을 사용하여 구현할 수 있다.

• heapq를 참조한다.
• n을 입력받는다.
• 카드 수를 저장할 배열 card를 선언한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> heapq의 heappush를 사용하여 card에 카드 수를 입력받는다. heappush를 하게 되면 지정된 우선순위로 자동 정렬된다. 지정된 우선순위가 따로 없다면 기본값인 오름차순으로 정렬된다.
• 결과값을 저장할 변수 answer를 0으로 정의한다.
• card의 길이가 1보다 클 동안 반복하는 while문을 돌린다. (길이가 1이면 돌지 않고 넘어간다.)
  -> 임시 변수 tmp1을 선언하고 heapq의 heappop()을 사용해 card에서 우선순위가 가장 높은 값을 tmp1에 넣어주고 card에서 제거한다.
  -> 임시 변수 tmp2를 선언하고 heapq의 heappop()을 사용해 card에서 우선순위가 가장 높은 값을 tmp2에 넣어주고 card에서 제거한다.
  -> answer에 tmp1+tmp2의 값을 더한다.
  -> heapq의 heappush()를 사용해 tmp1+tmp2를 card의 우선순위에 맞는 자리에 넣어준다.
• answer를 출력한다.

Code

import heapq
n=int(input())
card=[]
for i in range(n):
    heapq.heappush(card, int(input()))
answer=0
while len(card)>1:
    tmp1=heapq.heappop(card)
    tmp2=heapq.heappop(card)
    answer+=(tmp1+tmp2)
    heapq.heappush(card, tmp1+tmp2)
print(answer)