[백준] 15903번 카드 합체 놀이

문제: 15903번: 카드 합체 놀이

basic-algo-lecture/workbook/0x11.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x11.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
//#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    cin >> n >> m;
    // 최소힙으로 동작하도록..
    priority_queue<long long, vector<long long>, greater<long long>> cards;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        cards.push(tmp);
    }
    while (m-- > 0) {
        long long num1 = cards.top(); cards.pop();
        long long num2 = cards.top(); cards.pop();

        // 서로 더해서 다시 넣기
        cards.push(num1 + num2);
        cards.push(num1 + num2);
    }
    long long sum = 0;
    while (!cards.empty()) {
        sum += cards.top(); cards.pop();
    }
    cout << sum;

    return 0;
}

 

흠.. 그냥 최소힙 만든 다음에 while 문 돌면서 가장 작은 값 두개 빼고 서로 더한 후 다시 넣어주면 된다. 이렇게 하면 나중에 모든 카드를 다 더했을 때 최솟값이 나온다.