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

문제 소개

 

11497번: 통나무 건너뛰기

 

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

 

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

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

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

 

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

 

 

---

문제 풀이 전략

 

기획

 

 엄청 간단하다. 현재 가지고 있는 카드 중에서 가장 작은 카드 2개를 더하는 과정을 m번 반복하기만 하면 된다. 그러나, 가지고 있는 카드 중에서 가장 작은 카드 2개가 무엇인지 알아내는 것이 꽤 까다로울 수 있다. 이 문제를 해결하기 위해 아래의 설계에서 좀 더 자세한 방법을 알아보자.

 

 

설계

 

 C++의 STL에는 queue라는 라이브러리가 존재한다. 그리고 이 queue 라이브러리는 우선순위 큐라는 자료형을 제공한다. 우선순위 큐는 간단히 설명하자면, 큐와 비슷하게 pop, push, top 등의 기능을 가지고 있으나, 가장 우선순위가 높은 원소가 top에 위치하고 있다는 차이점이 있는 자료형이다.

 

priority_queue<int> descending_queue;
priority_queue<int, vector<int>, greater<int>> ascending_queue;

 우선순위 큐의 선언은 위와 같이 이루어진다. 내림차순으로 정렬하고자 하면(ex: 5 → 4 → 3 → ...) 위쪽 선언과 같이, 오름차순으로 정렬하고자 하면(ex: 1 → 2 → 3 → ...) 아래쪽 선언과 같이 작성하면 된다. 나머지 사용법은 일반적인 queue와 동일하다.

 

 

주의사항

 

 계속해서 더하는 문제의 특성상, 원소의 크기가 무척 커질 수 있다. 때문에 int가 아닌 long long을 사용해 주도록 하자. 글을 쓰는 필자도 계속해서 0%에서 틀리길래 무엇이 문제인가 했더니, 자료형의 크기가 문제였었다.

 

 

---

소스 코드

 

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

void scanData();
void solveProblem();
void printAnswer();

priority_queue<long long, vector<long long>, greater<long long>> cards;
long long n, m, tmp;
long long ans = 0;

int main()
{
    scanData();
    solveProblem();
    printAnswer();

    return 0;
}

void scanData()
{
    scanf("%lld %lld", &n, &m);

    for(int i = 0; i < n; i++)
    {
        scanf("%lld", &tmp);
        cards.push(tmp);
    }
}

void solveProblem()
{
    for(int i = 0; i < m; i++)
    {
        long long a = cards.top(); cards.pop();
        long long b = cards.top(); cards.pop();

        cards.push(a+b);
        cards.push(a+b);
    }

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

void printAnswer()
{
    cout << ans << endl;
}

 

 

---

테스트 케이스

 

[예제 1]
입력:
3 1
3 2 6

출력:
16



[예제 2]
입력:
4 2
4 2 3 1

출력:
19