[Algorithm]Baekjoon 15903 :: 카드 합체 놀이

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

15903번: 카드 합체 놀이

 
using namespace std;
 
int n, m;
long long input;
priority_queue<long long, vector<long long>, greater<long long>> pq;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
        pq.push(input);
    }
 
    while (m--)
    {
        if (pq.size() >= 2)
        {
            long long a = pq.top();
            pq.pop();
            long long b = pq.top();
            pq.pop();
 
            pq.push(a + b);
            pq.push(a + b);
        }
        else break;
    }
 
    long long answer = 0;
 
    while (!pq.empty())
    {
        answer += pq.top();
        pq.pop();
    }
 
    cout << answer;
}
 
 
 

 

임의의 카드 두개를 합치고, 합친값을 카드 두개에 덮어씌우는 것을 m번만큼 반복했을 때, 최솟값을 구하는 문제이다.

그냥 우선순위큐를 이용해서 제일 작은숫자들부터 합치면서 진행하면 되서 매우 쉬운문제다.