181. 카드 정렬하기

백준

1. 우선순위 큐

import heapq

n = int(input())

#힙에 초기 카드 묶음 모두 삽입
heap = []
for i in range(n):
  data = int(input())
  heapq.heappush(heap, data)

result = 0

#힙에 원소가 1개 남을 때까지
while len(heap) != 1:
  #가장 작은 2개의 카드 묶음 꺼내기
  one = heapq.heappop(heap)
  two = heapq.heappop(heap)

  #카드 묶음을 합쳐서 다시 삽입
  sum_value = one + two
  result += sum_value
  heapq.heappush(heap, sum_value)

print(result)

• 최소가 되려면 매 상황에서 가장 작은 크기의 두 카드 묶음을 꺼내서 이를 합친 뒤에 다시 리스트에 삽입하는 것이 최선이다.

• 매번 따로 비교를 하는 것보다 우선순위 큐를 사용하는 것이 훨씬 빠르다.

2. C++

#include <bits/stdc++.h>

using namespace std;

int n, result;
priority_queue<int> pq;

int main(void) {
    cin >> n;

    // 힙(Heap)에 초기 카드 묶음을 모두 삽입
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(-x);
    }

    // 힙(Heap)에 원소가 1개 남을 때까지
    while (pq.size() != 1) {
        // 가장 작은 2개의 카드 묶음 꺼내기
        int one = -pq.top();
        pq.pop();
        int two = -pq.top();
        pq.pop();
        // 카드 묶음을 합쳐서 다시 삽입
        int summary = one + two;
        result += summary;
        pq.push(-summary);
    }

    cout << result << '\n';
}