[python] 백준 1715 카드 정렬하기

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

 

문제 해결

• 작은 수의 카드 묶음의 크기를 가진 것 부터 계산을 하는 것이 이득이라는 것을 알 수 있다.
• 리스트를 쓰고 sort를 쓰면 시간 초과가 난다.
• 우선순위 큐 (heapq 나 PriorityQueue를 쓰면 좋겠다는 생각으로 풀었다.

 

CODE

import sys
import heapq
n = int(input())
A = []
for _ in range(n):
    heapq.heappush(A, int(input()))
ans = 0
while len(A)>1:
    a = heapq.heappop(A)
    b = heapq.heappop(A)
    c = a+b
    ans += c
    heapq.heappush(A,c)
print(ans)