[C++] 15903번: 카드 합체 놀이

링크

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

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)

출력

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

예제 입력 1 복사

3 1
3 2 6

예제 출력 1 복사

16

예제 입력 2 복사

4 2
4 2 3 1

예제 출력 2 복사

19

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

int main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	priority_queue<long long,vector<long long>, greater<long long>> card;
	long long result = 0;

	int n, m;
	cin >> n >> m;

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

	for (int i = 0; i < m; i++)
	{
		long long temp_1, temp_2, sum;
		temp_1 = card.top();
		card.pop();
		temp_2 = card.top();
		card.pop();
		sum = temp_1 + temp_2;

		card.push(sum);
		card.push(sum);
	}
	for (int i = 0; i < n; i++)
	{
		result += card.top();
		card.pop();
	}

	cout << result;
}

풀이

• 그리디 알고리즘을 사용해서 해결했다.
  
  
• 카드중 두 장을 골라 두 수를 더하고 더한 수를 각각의 카드에 다시 넣는 문제다.
  
  
• 수를 더해야 한다면 작은 수 끼리 더하는게 유리하기 때문에 오름차순으로 정렬된 카드의
  앞의 두 카드를 더해서 더한수를 다시 앞의 두 카드에 넣는 방법이 있다.
  
  
• queue를 이용하면 FIFO의 특성 때문에 먼저 들어간 수가 먼저 나오기 때문에
  작은 수를 맨 앞으로 오게 하여 pop을 하면 작은 수 부터 나오도록 하여야 한다.
  
  
• 큐를 정렬하려면 우선순위 큐를 사용해야 하니까  priority_queue를 사용하고,
  greater<> 를 이용해 작은수가 먼저 pop 되도록 한다.
  
  
• sort 함수에서는 기본이 오름차순이며 greater를 사용할 시 내림차순으로 정렬한다.
  다만 pq에서는 기본적으로 내림차순으로 정렬을 한다.
  greater를 이용하면 내림차순이 아닌 오름차순으로 정렬을 한다.