[백준] 1715 카드 정렬하기 c++

 

문제 링크 https://www.acmicpc.net/problem/1715

KEY

• 우선순위 큐를 활용하는 간단한 문제이다.
• 두 카드묶음을 선택할 때, 순서대로 고르지 않아도 되고 무작위로 두개를 선택해도 되므로, 스택(stack)이 아닌 우선순위 큐(priority_queue)를 사용한다.

N의 조건이 1부터 100,000이라서 N이 1일때도 고려해야 하는데 1일때를 고려해서 풀면 오히려 오답이 나온다..🤔

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
int N;
vector<int> v;
priority_queue<int, vector<int>, greater<>> pq;
int answer;
 
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int card;
        cin >> card;
        pq.push(card);
    }
    while (pq.size() >= 2) {
        //가장 작은 카드묶음 2개 선택
        int first = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();
 
        //합을 push
        pq.push(first + second);
        
        answer += (first + second); 
    }
    cout << answer;
}