15903번 - 카드 합체 놀이(c++)

🗒 15903번 문제

📌 priority Queue를 사용해서 오름차순의 큐를 받아라 ❗️

  1️⃣ 카드 합체 놀이 문제는 서로 다른 카드 두 장을 m번 합체 시켜서 최소 점수를 만들어야 한다.

  2️⃣ 가장 작은 값끼리 계속 합체하는 경우가 가장 작은 값을 만든다.

  3️⃣ priority queue는 내림차순으로 큐가 정렬되어 있기에 오름차순으로 값을 받아내기 위해서는 -(값)을 넣어준다.

  4️⃣ top에 있는 값을 연속 두번 꺼내서 그 두 값을 더하고 그 합을 큐에 다시 넣는다.
  
  5️⃣ 합해서 들어간 값은 그 값의 위치에 맞게 들어가 진다. -> priority queue이기에!
  
  6️⃣ 들어가는 자연수 값이 1,000,000까지 가능하기에 들어가는 값을 long long 타입으로 선언하자.
     

➰ 코드로 나타낸 15903번 ➰

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    priority_queue<long long> pq;
    int n, m;
    long long num, answer = 0;
    
    cin >> n >> m ;
    // 먼저 숫자들을 받는다.
    while (n--) {
        cin >> num;
        pq.push(-num);
    }
    
    // 합체 가능 횟수만큼 while문을 돌리자
    while (m--) {
    	// 첫번째 top, 두번째 top를 저장하고 두 값을 queue에서 뺀다.
        // 그 두 값의 합을 큐에 두 번 저장 -> 카드 두개의 값이 변경되었기에
        long long first = -pq.top();
        pq.pop();
        long long second = -pq.top();
        pq.pop();
        long long sum = first + second;
        pq.push(-sum);
        pq.push(-sum);
    }
    
    while (!pq.empty()) {
        answer += (-pq.top());
        pq.pop();
    }
    cout << answer << endl;
    return 0;
}