[백준] 15903번 카드 합체 놀이 (C++)

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

 

 

이 문제는 n개의 카드가 존재할때 임의의 서로 다른 카드 2장을 선택해서 더한 뒤 그 값을 2장의 카드에 대해 덮어 씌워 

모든 카드를 더했을때 가장 작은 수를 출력하는 문제이다.

 

그렇다면 생각해야할 것은 서로 다른 2장의 카드를 선택해서 가장 작게 만들어 덮어 씌우면 최소가 된다는 생각을 할 수 있다.

 

그럼 가장 작은 수를 선택하기 위해서 정렬을 하거나 최소힙을 사용해서 하는 방법이 있다.

 

필자는 최소힙을 사용하여 가장 작은 2개를 꺼내서 합한 뒤 다시 힙에 넣어주는 방식을 사용하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, M;
priority_queue<ll, vector<ll>, greater<ll>> pq;

void solve() {
    for(int i = 0; i < M; i++) {
        ll a = pq.top();
        pq.pop();
        ll b = pq.top();
        pq.pop();
        ll tmp = 0;
        tmp += a + b;
        pq.push(tmp);
        pq.push(tmp);
    }

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

    cout << answer;
}

void input() {
    cin >> N >> M;

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


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

    input();
    solve();
}