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

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

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	priority_queue<int, vector<int>, greater<int>> q;
	int n, sumCount = 0, result = 0;

	cin >> n;

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

	while(q.size() > 1)	//카드 더미가 하나 이하일 경우는 비교할 필요가 없다.
	{
		int curr = q.top();
		q.pop();
		int next = q.top();
		q.pop();

		result += curr + next;
		q.push(curr + next);
	}

	cout << result;
}

풀이

우선순위 큐에 카드 더미를 넣어서 더미의 개수가 작은 순으로 더해나간다.

3 10 20 40일경우

10 20 40 - 30 40 - 70 //큐의 상태

  30    +   70   =  100

4 10 20 40 50일경우

10 20 40 50 - 30 40 50 - 50 70 - 120

  30        +      70    +     120  =  220

 

이런식으로 계산된다.

 

문제의 중요포인트

- 최소힙을 이용하여 작은 두 수가 가장 앞에 오도록한다.

- 작은 두수의 합을 저장해나간다.