백준 1715 <카드 정렬하기> Python

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

---

먼저 합친 카드패를 연속해서 더하게 되는 방식이므로 작은 패부터 더해주는 것이 최적의 수가 되는 전형적인 그리디 알고리즘 문제입니다.

다만 여러 패들 중에 더한 패를 들고 계속 더하는 것이 아닌 더한 패를 다시 패들 속에 섞고 그들 중 가장 작은 패 두개를 더하는 방식으로 여러 번 진행해야 합니다.

즉 추가하고 뽑고를 반복해야 하니 효율적인 진행을 위해 우선순위큐를 사용하는 것이 합리적입니다.

---

import sys
import heapq

input = sys.stdin.readline


def solution(N, bundles):
    # 번들 리스트 힙으로 치환
    heapq.heapify(bundles)
    # 카운트
    cnt = 0
    # 모든 번들을 합할 때 까지
    while len(bundles) > 1:
        # 두 개의 번들
        first_bundle = heapq.heappop(bundles)
        second_bundle = heapq.heappop(bundles)
        # 새로운 번들
        new_bundle = first_bundle + second_bundle
        # 추가
        heapq.heappush(bundles, new_bundle)
        # 카운트 추가
        cnt += new_bundle

    print(cnt)


# 입력
N = int(input().strip())
bundles = [int(input().strip()) for _ in range(N)]

solution(N, bundles)

코드