[백준 C++] 1715 카드 정렬하기 - 그리디

1715번: 카드 정렬하기

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<int>> Cards;

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

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int Card;
		cin >> Card;
		Cards.emplace(Card);
	}

	int Cnt = 0;
	for (int i = 0; i < N - 1; ++i)
	{
		int First = Cards.top();
		Cards.pop();

		int Second = Cards.top();
		Cards.pop();

		int NewCard = First + Second;
		Cards.emplace(NewCard);

		Cnt += NewCard;
	}

	cout << Cnt;
}

---

 

카드 묶음을 합칠 때 매번 값이 가장 작은 두 카드묶음을 선택하도록 푸는 문제입니다.

따라서 오름차순 우선순위 큐를 이용해서 간단하게 풀 수 있습니다.

주의할 점은 합친 카드묶음을 큐에 다시 넣어주어야 합니다.