테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 카드 정렬하기 ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}