[15903] 카드 합체 놀이

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

15903번: 카드 합체 놀이

<문제>

그리디적으로 생각해서, 가장 작은거 두개를 골라서 연산을 진행해주면 된다.

이를 m번 반복해야하는데, 항상 필요한건 작은거 2개이므로 우선순위큐를 사용하여 구현하면 편리하다.

 

<소스코드>

#include <stdio.h>
 
#include <algorithm>
#include <queue>
using namespace std;
priority_queue<long long> q;
int n, m;
int main(void) {
    int i, j, cnt = 0;
    long long y, x, temp, sum = 0;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        scanf("%lld", &temp);
        sum += temp;
        q.push(-temp);
    }
 
    while (cnt < m) {
        y = -q.top();
        q.pop();
        x = -q.top();
        q.pop();
        sum += (y + x);
        q.push(-(y + x));
        q.push(-(y + x));
        cnt++;
    }
    printf("%lld", sum);
    return 0;
}