[백준] C++ 1715(카드 정렬하기)

#include <iostream>
#include <queue>

using namespace std;

priority_queue <int> Q;

int main(void)
{
	int a=0;
	cin>>a;
	
	for(int i=0; i<a; i++)
	{
		int num=0;
		cin>>num;
		Q.push(-num);
	}
	
	int sum=0;
	
	while(Q.size()>1)
	{
		int num1=Q.top();
		Q.pop();
		int num2=Q.top();
		Q.pop();
		Q.push((num1+num2));
		sum=sum-(num1+num2);
	}
	
	cout<<sum;
	return 0;
}

이 문제는 카드 합치기 문제이다. 카드 A와 카드 B를 합치려면 A+B만큼의 연산이 필요하다고 한다.

카드 묶음이 주어지면 최소한 몇 번의 비교가 필요한가??

 

문제 예시에서는 10,20,30,40를 예로 들고 있다. (10+20)+(30+40)이 최소인 것을 쉽게 알 수 있다.

위를 보고 작은 것들끼리 계속 더하는 것이 문제를 해결하는 방법임을 깨달아야 한다.

작은 것들끼리 어떻게 계속 더하려면 어떤 자료구조가 필요할까?

*우선순위 큐*가 필요하다. 우선순위 큐는 우선이 되는 노드를 가장 앞에 두는 큐를 말한다.

이렇게 하면 큐에서 계속해서 제일 작은 노드 두 개를 빼는 것이 가능하다.

 

일반적으로 priority_queue <int> Q;이렇게 선언을 하고 큐에 push를 하게 되면 큐에는 큰게 우선으로 들어간다.

40,30,20,10 이렇게 말이다.

그런데 우리가 필요한 것은 가장 작은 숫자가 2개 필요하다. 어떻게 하면 작은 숫자가 우선이 되게 만들 수 있을까??

push를 할 때 -를 붙여서 push를 해주는 것이다. 그럼 -10,-20,-30,-40 이렇게 들어가게 된다.

이러한 방식으로 큐에 사이즈가 1이 될 때까지 계속해서 while문을 반복해 주면 된다. 

 (힙 정렬과 굉장히 흡사하다. 찾아보는 것이 도움이 될 것이다.)