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

1. 제목

- 백준 15903 카드 합체 놀이

- BOJ 15903 카드 합체 놀이

 

문제 링크 : 15903번: 카드 합체 놀이 (acmicpc.net)

15903번: 카드 합체 놀이

---

2. 풀이 과정

 

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

 

이문제에서 핵심 문장이라고 생각합니다. N개의 카드들 중 2개를 선정해서 합체를 하면 2개의 카드가 모두 같은 숫자가 된다는 규칙이 있기 때문에 가장 작은 숫자의 카드끼리 합체를 하는 게 유리합니다. 그렇기에 이문제는 카드들을 오름차순으로 정렬하고 가장 작은 숫자의 카드 2장을  합치 고를 M번 반복하는 방법으로 풀었습니다. 정렬방법으로는 우선순위큐를 이용하여 큐에 넣을 때 카드들이 정렬되게 했습니다.

 

1. 우선순위큐에 카드를 넣는다.
2. 가장 작은 숫자의 카드 2장을 골라 우선순위큐에서 빼고 합친다음 다시 우선순위큐에 넣는다

---

3. 코드

// 1. 우선순위큐에 카드를 넣는다.
// 2. 가장 작은 숫자의 카드 2장을 골라 우선순위큐에서 빼고 합친다음 다시 우선순위큐에 넣는다

#include <iostream>
#include <queue>
#include <functional>

using namespace std;

int main()
{
    int n, m;
    priority_queue <long long, vector<long long>, greater<long long>> cards;

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        long long card;
        cin >> card;

        // 1. 우선순위큐에 카드를 넣는다.
        cards.push(card);
    }

    for (int i = 0; i < m; i++)
    {
        // 2. 가장 작은 숫자의 카드 2장을 골라 우선순위큐에서 빼고 합친다음 다시 우선순위큐에 넣는다
        long long card1 = cards.top();
        cards.pop();
        long long card2 = cards.top();
        cards.pop();

        long long mergeCard = card1 + card2;
        cards.push(mergeCard);
        cards.push(mergeCard);
    }

    long long result = 0;
    for (int i = 0; i < n; i++)
    {
        result += cards.top();
        cards.pop();
    }

    cout << result << endl;

    return 0;
}