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

 

#include <iostream>
#include <queue>

using namespace std;

priority_queue<long long int> Q;

int main(void)
{
	int n=0;
	int m=0;
	
	cin>>n>>m;
	
	for(int i=0; i<n; i++)
	{
		int num=0;
		cin>>num;
		Q.push(-num);
	}
	
	for(int i=0; i<m; i++)
	{
		long long int num1=Q.top();
		Q.pop();
		long long int num2=Q.top();
		Q.pop();
		
		long long int temp=num1+num2;
		Q.push(temp);
		Q.push(temp);
	}
	
	long long int sum=0;
	
	while(!Q.empty())
	{
		sum+=Q.top();
		Q.pop();
	}
	
	cout<<-sum;
	
	
	
	return 0;
}

 

아기 석환이를 위해 가장 작은 점수를 구해주자!

조건

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

두장을 뽑고 두장을 더한다? 그리고 그 합을 덮어쓴다? 최솟값을 구한다??

이 조건을 보고 나면 이런 생각이 들것이다.

가장 작은 카드를 두 개 뽑아서 합쳐주는 것을 반복하면 되겠는데??

 

그렇다 가장 작은 카드를 뽑아서 합쳐주는 작업을 계속하면 최솟값을 구할 수 있다.

 

1. 카드를 우선순위 큐에 넣는다.

2. 가장 작은 카드를 두 개 뽑고 더한다. 그리고 덮어쓴다.

3. 덮어쓴 카드를 다시 우선순위 큐에 넣는다.

4. 위 작업을 n번 반복한다.