1715 카드 정렬하기

1715. 카드 정렬하기 / c++ / Gold 4 / 13분

문제

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

1. 카드를 두 묶음씩 섞는다.
2. 마지막 한 장의 카드 더미가 남을 때 가장 적게 섞은 횟수는?

접근 방식

그리디, 우선순위 큐

1. 우선 카드를 가장 적게 섞으려면, 가장 적은 카드 둘을 골라 섞으면 된다.
   (즉, 매번 가장 적은 수를 골라야 하므로, 그리디)
2. 카드를 입력 받을 때 우선순위 큐를 사용한다.
   (따로 정렬이 필요 없음, 맥스힙이기 때문에, ‘-‘를 붙여서 사용)
3. 우선순위 큐의 제일 위 카드 더미 두개를 꺼내 합치고, 그 값을 answer에 더해준다. 그리고 다시 우선순위 큐에 넣는다.
4. 마지막에 -answer을 출력

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>
using namespace std;

int N, num;
priority_queue<int> pq;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> num;
        pq.push(-num);
    }

    int answer = 0;

    while (pq.size() != 1)
    {
        int sum = pq.top(); pq.pop();
        sum += pq.top(); pq.pop();
        answer += sum;
        pq.push(sum);
    }

    cout << -answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. 항상 ‘가장 작은’ 카드 더미를 선택하므로 ‘그리디’
2. 지금 보니, 그리디는 우선순위 큐와 참 찰떡이다.
3. 우선순위 큐는 Max Heap이므로, Min Heap으로 사용하고 싶다면, 원소에 ‘-‘ 붙여서 사용하자.