[백준 / BOJ] C++ 1715 카드 정렬

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

1715번: 카드 정렬하기

풀이

우선순위 큐를 사용하는 간단한 문제이다.

우선순위 큐에 입력된 카드 갯수를 하나씩 push 해준 이후, top 의 원소 2개를 먼저 더해주고 

해당 큐가 비어있지 않다면 push 해주어 다음 원소와 더한 값들을 결과값에 넣어주면 된다.

 

Code ( C++ )

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    priority_queue<int, vector<int>, greater<int>> pq;

    cin >> N;

    int cardNum = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> cardNum;

        pq.push(cardNum);
    }

    //do {
    //
    //} while (!pq.empty());

    if (N == 1)
    {
        cout << "0" << "\n";
        return 0;
    }

    int result = 0;
    while (!pq.empty()) 
    {
        int sum = 0;
        sum += pq.top();
        pq.pop();
        if (!pq.empty()) {
            sum += pq.top();
            pq.pop();
            if (!pq.empty())
                pq.push(sum);
        }

        result += sum;
    }

    cout << result << "\n";
}