[백준][C++] 15903: 카드 합체 놀이

문제

15903번: 카드 합체 놀이

풀이

그리디, 우선순위 큐

 

• 가장 작은 수를 만들기 위해서는 뽑는 카드가 현재 상태에서 가장 작은 2장의 카드를 뽑아야 한다(그리디).
• 현재 상태에서 가장 작은 카드를 뽑기 위해 우선순위 큐를 사용한다. 
• 우선순위 큐의 탑에 있는 카드를 2장 뽑는다.
• 2장의 카드를 더한 값을 우선순위 큐에 2번 더한다. 
• 이를 m번 반복한다.

여기서 카드의 수가 크기때문에 자료형은 long long을 사용해야 한다.

코드

#include <iostream>
#include <queue>

using namespace std;

priority_queue<long long, vector<long long>, greater<long long>> pq;

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

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

    for (int i = 0; i < n; ++i)
    {
        int temp;
        cin >> temp;
        pq.push(temp);
    }

    while (m--)
    {
        // 가장 작은 카드 2개를 뽑는다.
        long long card1 = pq.top();
        pq.pop();
        long long card2 = pq.top();
        pq.pop();

        // 뽑은 카드를 더한 값을 2번 넣는다.
        long long sum = card1 + card2;
        pq.push(sum);
        pq.push(sum);
    }

    long long answer = 0;
    while (!pq.empty())
    {
        answer += pq.top();
        pq.pop();
    }

    cout << answer;
    
    return 0;
}