카드 정렬하기

• 그리디한 방식으로 가장 작은 묶음 두개를 골라서 합치는 것을 반복하는 것이 최적이다.
• 가장 작은 묶음을 꺼내고, 새 묶음을 추가하는 작업은 우선순위 큐 (Priority Queue)를 통해서 처리하면 된다. pop과 push 모두 O(logn)이 걸린다. 이렇게 두 묶음을 합치는 작업을 n-1번 해야지 한묶음이 되므로, 총 시간복잡도는 O(nlogn)

"""Solution code for "BOJ 1715. 카드 정렬하기".

- Problem link: https://www.acmicpc.net/problem/1715
- Solution link: http://www.teferi.net/ps/problems/boj/1715

Tags: [Priority queue]
"""

import heapq
import sys


def main():
    N = int(sys.stdin.readline())
    size_heap = [int(sys.stdin.readline()) for _ in range(N)]

    heapq.heapify(size_heap)
    answer = 0
    for _ in range(N - 1):
        s1 = heapq.heappop(size_heap)
        s2 = heapq.heappop(size_heap)
        answer += s1 + s2
        heapq.heappush(size_heap, s1 + s2)        

    print(answer)


if __name__ == '__main__':
    main()