[백준] 1715 카드 정렬하기

1715번: 카드 정렬하기

 

www.acmicpc.net

풀이

가장 작은 숫자의 카드끼리 섞어야한다는 것은 직관적으로 알 수 있다. 따라서 우선순위 큐를 사용해서 구현했다.

코드

C++

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        pq.push(tmp);
    }

    int ans = 0;
    while (pq.size() > 1) {
        int n1 = pq.top();
        pq.pop();
        int n2 = pq.top();
        pq.pop();
        int sum = n1 + n2;
        ans += sum;
        pq.push(sum);
    }
    cout << ans << '\n';
    return 0;
}

Python3

import sys
import heapq

n = int(sys.stdin.readline().strip())
card = []

for i in range(n):
    heapq.heappush(card, int(sys.stdin.readline().rstrip()))

answer = 0
while len(card) > 1:
    a = heapq.heappop(card)
    b = heapq.heappop(card)
    answer += (a + b)
    heapq.heappush(card, a + b)
print(answer)