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

문제

[C++] 백준 1715: 카드 정렬하기 GOLD 4
https://www.acmicpc.net/problem/1715

 

---

 

접근 방법

이 문제는 여러 묶음의 카드가 주어졌을 때, 모든 카드를 하나로 합치는 데 필요한 비교 횟수의 최소값을 구하는 문제이다.

핵심 아이디어는 항상 가장 작은 두 묶음을 먼저 합치는 것이다.
두 묶음을 합칠 때 발생하는 비교 횟수는 두 묶음의 크기 합이고, 이 값은 이후에도 계속 누적되기 때문에 작은 값부터 처리해야 전체 합이 최소가 된다.

 

이를 효율적으로 구현하기 위해 우선순위 큐(priority_queue) 를 사용했다.

• 모든 카드 묶음을 우선순위 큐에 넣는다. (오름차순)
• 큐에서 가장 작은 두 값을 꺼내 합친다.
• 그 합을 결과에 더하고, 다시 큐에 넣는다.
• 큐에 하나만 남을 때까지 반복한다.

이 방식은 허프만 트리(Huffman Coding) 와 동일한 그리디 전략이다.

 

구현 시 주의할 점

• 기본 priority_queue는 내림차순이므로,
  greater<int>를 사용해 오름차순 큐로 만들어야 한다.
• 매번 두 개를 꺼내고 다시 하나를 넣기 때문에, 큐의 크기가 1이 될 때까지 반복해야 한다.

 

---

 

코드

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

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

	int n = 0;
	cin >> n;

	priority_queue<int, vector<int>, greater<int>> pq;  // 오름차순
	int t = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> t;
		pq.push(t);
	}
	int sum = 0;
	while (pq.size() > 1)
	{
		int first = pq.top();
		pq.pop();
		int second = pq.top();
		pq.pop();

		sum += (first + second);
		pq.push(first + second);
	}
	cout << sum;

	return 0;
}