[C++] 백준 온라인 저지 15903번 카드 합체 놀이 풀이

숫자가 써진 카드를 규칙에 따라 합쳤을 때 카드에 써진 숫자들의 최소 합을 구하는 문제

 

---

문제

 

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

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

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

 

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

 

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

 

 

풀이

 

 문제의 의도대로 최소 합을 만드려면 가장 작은 숫자끼리 더하고 덮어 씌우기를 반복해야 합니다. 그래서 이 때 적절한 컨테이너는 바로 우선순위 큐! 우선순위 큐로 최소힙을 만들어 줍니다. 그러면 오름차순으로 정렬되어 가장 작은 숫자가 맨 앞으로 올 것이고 맨 앞 두 숫자를 꺼내서 더한 뒤 다시 큐에 삽입해 주면 되겠죠. 

 

 최소힙으로 정렬된 큐의 맨 앞 두 숫자를 꺼내 더한 다음 큐에 2번 삽입하는 과정을 m번 반복합니다. 그 다음 큐에서 숫자를 하나씩 꺼내 더한 누적합계를 출력하면 끝~

 

 이 때 주의 사항은 자료형을 int가 아닌 long long으로 선언해 주셔야 합니다. 입력으로 주어지는 수의 범위는 int로 표현할 수 있는 범위이지만 m의 최대값인 15xn번만큼 더하다 보면 int의 표현 범위를 넘어갈 수 있거든요. 

 

 

코드

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    
    //최소힙
    //오버플로우를 막기 위해 long long으로 선언
    priority_queue<long long, vector<long long>, greater<long long>> numbers;
    for (int i = 0; n > i; i++)
    {
        long long input;
        cin >> input;
        numbers.emplace(input);
    }
    
    //맨 앞 숫자 2개를 꺼내 더한 다음 큐에 2번 삽입한다.
    for (int i = 0; m > i; i++)
    {
        auto first = numbers.top();
        numbers.pop();
        auto second = numbers.top();
        numbers.pop();
        
        auto sum = first + second;
        for (int j = 0; 2 > j; j++)
            numbers.emplace(sum);
    }
    
    long long answer = 0;
    while (!numbers.empty())
    {
        answer += numbers.top();
        numbers.pop();
    }
    
    cout << answer;
    
    return 0;
}