[BOJ] C++ 15903 카드 합체 놀이 - 우선순위 큐와 오버플로우 조심하기

예제 1

3 1
3 2 6

answer : 16

예제 2

4 2
4 2 3 1
 
answer : 19

---

n개의 카드에 대해 어떤 두 카드의 숫자를 그 두 카드의 합으로 바꾸는 것을 m번 진행한 뒤 n개의 카드의 숫자 합이 최소가 되게 하는 문제이다. 먼저 그리디 하게 매 턴마다 가장 작은 숫자 두 개를 고르면 된다고 생각했다. 

 

매 턴마다 그리디 하게 숫자를 고르는 것까지는 문제가 없어 보였고, 구현 부분은 우선순위 큐를 이용해 간단히 우선순위를 내림차순으로 하고, pop 두 번 후 두 숫자를 더한 값을 push 두 번 하는 식으로 구현했다.

 

여기까지는 쉬웠지만 주의할 점이 하나 있었다. n개의 카드가 최대 1,000개이고 15 * n번의 턴이 진행되며 각 카드의 숫자는 최대 1,000,000여서 int 자료형으로 구현하게 되면 오버플로우가 발생한다. 따라서 모든 자료형을 long long으로 바꿔주었다. 자료형을 long long으로 바꿀 때 연산 과정에서 일부 int가 섞여있으면 계산에 오류가 발생할 수 있으므로 콤팩트하게 다 바꿔주자.

 

/** 우선순위 큐 15903 카드 합체 놀이  **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

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

    int n, m;
    cin >> n >> m;

    priority_queue<long long, vector<long long>, greater<long long>> cards;
    long long sum = 0;
    for (int i = 0; i < n; i++)
    {
        long long temp;
        cin >> temp;
        cards.push(temp);
        sum += temp;
    }

    for (int i = 0; i < m; i++)
    {
        long long a = cards.top();
        cards.pop();
        long long b = cards.top();
        cards.pop();
        // a, b에 각각 우선순위 큐의 가장 작은 값 2개 저장
        sum += a + b;
        cards.push(a + b);
        cards.push(a + b);
    }

    cout << sum << "\n";
}