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

문제

1715번: 카드 정렬하기

풀이

그리디, 우선순위 큐

 

카드 수가 가장 적은 2개의 묶음을 합치는 방식으로 해결할 수 있다. 이 때, 2개의 묶음을 선택하기 위해, 우선순위 큐를 사용한다. 

1. 카드 수가 가장 적은 2개의 묶음을 합친다.
2. 합쳐진 묶음을 다시 우선순위 큐에 넣는다.
3. 모든 카드 묶음이 합쳐질 때까지 반복

코드

#include <iostream>
#include <queue>

using namespace std;

// 오름차순 우선순위 큐
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

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

        pq.push(temp);
    }

    // 카드 수가 가장 적은 2개의 묶음을 합친다.
    // 합쳐진 묶음을 다시 우선순위 큐에 넣는다.
    // 모든 카드 묶음이 합쳐질 때까지 반복
    int answer = 0;
    while (pq.size() > 1)
    {
        int deck1 = pq.top();
        pq.pop();
        int deck2 = pq.top();
        pq.pop();

        answer += (deck1 + deck2);

        pq.push((deck1 + deck2));
    }

    cout << answer;

    return 0;
}