[C++] 백준/Silver/15903. 카드 합체 놀이

문제: 카드 합체 놀이 (백준 15903번)

문제 분석

N장의 카드가 있고, 각 카드에 적힌 숫자가 주어진다.
카드 합체 놀이에서는, 매번 두 장의 카드를 골라 그 합을 계산한 뒤, 두 카드 모두 그 합으로 교체한다.
이를 총 M번 반복한 후, 모든 카드에 적힌 숫자의 합을 구하는 문제이다.

---

핵심 포인트:

• 최소 힙 활용:
  매 번 가장 작은 두 수를 선택하면, 앞으로의 합산 결과가 최소가 되어 최종 결과에 큰 영향을 미치게 된다.
  그래서 최소 힙(우선순위 큐)를 사용하여 O(M log N)의 효율적인 계산을 할 수 있다.
• 알고리즘 흐름:
  1. 모든 카드 값을 최소 힙에 넣는다.
  2. M번 동안, 힙에서 가장 작은 두 수를 꺼내 합을 구하고, 그 합을 다시 힙에 두 번 넣는다.
  3. 모든 연산이 끝나면 힙에 남은 모든 카드의 값을 합산한다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;

    // 최소 힙: 가장 작은 값이 우선순위
    priority_queue<long long, vector<long long>, greater<long long>> pq; 

    // 카드 값 입력
    for (int i = 0; i < n; i++)
    {
        long long x;
        cin >> x;
        pq.push(x);
    }

    // m번의 카드 합체 연산
    while (m--)
    {
        long long a = pq.top(); 
        pq.pop();
        long long b = pq.top(); 
        pq.pop();
        
        long long sum = a + b;
        // 선택한 두 카드 모두 합으로 갱신
        pq.push(sum);
        pq.push(sum);
    }

    // 최종 카드 합계 계산
    long long result = 0;
    while (!pq.empty())
    {
        result += pq.top();
        pq.pop();
    }

    cout << result;
}