BOJ 15903 : 카드 합체 놀이

• 문제 링크 : boj.kr/15903
• 난이도 : S1
• 태그 : 그리디, 우선순위 큐

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n, m;
    cin >> n >> m;
    priority_queue<ll> _pq;
    for(int i = 0; i < n; i++) {
        ll input;
        cin >> input;
        _pq.push(-input);
    }
    for(int i = 0; i < m; i++) {
        ll a = _pq.top(); _pq.pop();
        ll b = _pq.top(); _pq.pop();
        _pq.push(a+b);
        _pq.push(a+b);
    }
    ll ans = 0;
    while(!_pq.empty()) {
        ans += -_pq.top();
        _pq.pop();
    }
    cout << ans;
    return 0;
}

---

풀이

합체 과정을 통해 a_i, a_j를 골랐다면 전체 카드의 합에 a_i와 a_j가 더해진다.

따라서 가장 작은 두 수를 가진 카드를 합체해주는 것이 최적이다.