[백준/C++] 1715번 카드 정렬하기

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

1715번: 카드 정렬하기

골드4티어 문제치고는 좀 쉽다는 생각이 들었다. 요즘 빡센 bfs 구현문제만 풀어서 그런가..? 싶지만 자만하지 말자..

우선순위 큐를 하나 선언하는데, 기본 값은 내림차순(큰 값이 우선) 이므로 오름차순으로 정렬되도록 선언해준다!

​

그리고 제일 작은 것과 그 다음 작은 것 2개를 가져와서 더한 후, 다시 큐에 넣는다. 이 때 정답은 누적합으로 구해준다.

큐가 비거나 하나밖에 없다면(= 비교가 끝났다면) 이때까지 누적합으로 구한 비교횟수를 출력해준다!

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<string>
#include<cctype>
#include<cmath>

using namespace std;

priority_queue<int,vector<int>,greater<>> pq;
int n,ans,tmp;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;

    for(int i=0; i<n;i++){
        int card;
        cin >> card;
        pq.push(card);
    }

    while(!pq.empty()){
        int first = pq.top();
        pq.pop();

        if(pq.empty()) break;

        int second = pq.top();
        pq.pop();

        tmp = first+second;
        ans += tmp;
        pq.push(tmp);
    }
    cout << ans;
    return 0;
}