[백준 1751 C++] 카드 정렬하기 풀이(그리디, 우선순위 큐)

처음에는 ATM 문제처럼 sort 정렬을 생각했는데, 생각해보니 값이 계속 갱신되면서 작은 값끼리 더해야 하기때문에 한번 sort로는 부족하다.

 

(처음 오답 코드)

“항상 가장 작은 두 묶음”을 계속 골라야 하는데, 한 번 정렬하고 그대로 앞에서만 더함

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int N;
    cin >> N;
    int card[100001];
    for(int i=0; i<N; i++){
        cin >> card[i];
    }
    sort(card, card+N); 
    int sum = 0, answer = 0;
    for(int i=0; i<N-1; i++){
        sum = card[i] + card[i+1];
        card[i+1] = sum; 
        answer += sum;
    }

    cout << answer;

}

 

우선순위 큐를 사용해서 최소 힙은 먼저 꺼내도록 하자!

 

정답 코드

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

int main(){
    int N, answer = 0;
    priority_queue<
                    int,         // 자료형
                    vector<int>, // 내부 컨테이너
                    greater<int> // 정렬 기준 - 작은 값이 우선순위 높음
                    > pq; 
    // 작은 값 먼저 꺼냄
    cin >> N;
    if(N == 1){
        cout << 0;
        return 0;
    }
    for(int i=0; i<N; i++){
        int temp;
        cin >> temp;
        pq.push(temp);
    }

    while(pq.size() > 1){
        int a = pq.top(); pq.pop(); // 가장 작은 값 꺼냄
        int b = pq.top(); pq.pop();
        answer += a + b;
        pq.push(a + b); // 합쳐진 카드 다시 넣음
    }

    cout << answer;

}