[코딩테스트] [BOJ1715] 카드 정렬하기

문제

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

---

풀이

1. 우선순위 큐로 최소 힙을 생성하여 입력값을 관리한다.

2. 가장 작은 수 2개를 순차적으로 합쳐서 횟수를 계산해야 하기 때문에, 큐의 원소가 2개 이상일 때 반복한다.
   2-1. top에 있는 수와 그 다음으로 큰 수를 합하기 위해 pop을 해줘서 두 숫자 모두 큐에서 제거한다.
   2-2. 2-1에서 꺼낸 두 수를 더해주고, 이를 큐에 다시 push해 오름차순으로 정렬한다.

+) 만약 큐에 원소가 하나 남았다면, 이전에 계산된 두 수의 합이기 때문에 더해줄 필요가 없다.

---

코드

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

int main()
{
    int n = 0;
    cin >> n;

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

    long long sum = 0;
    while (minQueue.size() > 1)
    {
        long long current = 0;
        for (int i = 0; i < 2; i++)
        {
            current += minQueue.top();
            minQueue.pop();
        }
        
        sum += current;
        minQueue.push(current);
    }

    cout << sum;

    return 0;
}