[백준] 15903번: 카드 합체 놀이

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

15903번: 카드 합체 놀이

오늘 문제는 Greedy 알고리즘 카테고리에 있던 문제다.

풀이는 아래 코드를 확인하자!

 

(기본 아이디어 베이스)

결국 최종 카드 합체 놀이가 끝나고 난 결과들을 다 더했을 때 최소가 되려면 애당초 합체 놀이를 진행할 때 작은 수들만 2개 골라 더해가면 된다.

1. 그러면 항상 작은 순서대로 수들을 정렬해두자.

2. 가장 작은 2개의 수들을 뽑고 이 결과를 다시 배열에 담아두자.

 

그래서 나는 우선순위 큐를 이용해 항상 오름차순 하도록했다.

while(m--)을 통해 합체 횟수 m번 진행하도록 했으며 card에서 2번 pop()하고 2번 push한 이유는

항상 카드를 두 장 뽑고 더한뒤 그 결과를 뽑은 두 장의 덮어쓰므로 두 장 뽑는건 top()을 통해 뽑아서 pop()으로 지우고

2장 합을 2번 push()한다면 이는 덮어쓰는 거랑 같은 의미가 되기 때문이다.

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

#define FastIO ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

using namespace std;

int main(void)
{
	FastIO;

	int n = 0, m = 0; // 카드의 개수 n, 합체 횟수 m
	cin >> n >> m;

	priority_queue<long long, vector<long long>, greater<long long>> card;

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

	while (m--)
	{
		long long smFirst = card.top();
		card.pop();
		long long smSecond = card.top();
		card.pop();
		
		long long sum = smFirst + smSecond;
		card.push(sum);
		card.push(sum);
	}

	long long result = 0;
	while (!card.empty())
	{
		result += card.top();
		card.pop();
	}

	cout << result << "\n";
	return 0;
}