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

각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 

 

이 문제를 보고 딱 떠올려야 하는 것은 그리디하게 접근해야 한다는 것이다. 예를 들어보자 .

 

카드의 수가 "2, 3, 4, 10, 100"의 묶음이 존재한다. 

여기서 직관적으로 어떻게 해야 두 묶음을 합친 것이 최솟값이 되는지 보여야한다. 

 

즉, 작은 수 부터 골라서 그 값을 합쳐야 한다. 

 

(2+3), 4, 10, 100 -> (4+5), 10, 100 -> (9+10) , 100 -> (19 + 100)

 

 priority_queue 를 최소힙으로 생성하여 최상단에 위치한 두개의 데이터 값을 합해서 다시 push 해준다. 

<priority_queue> 자료구조

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std; 
int main() {
	priority_queue <int, vector<int>, greater<int>> q;
	int n; cin >> n; 
	for (int i = 0; i < n; i++) {
		int a; cin >> a; 
		q.push(a); 
	}
	int sum = 0; 
	while (q.size() > 1) {
		int x = q.top(); 
		q.pop(); 
		int y = q.top(); 
		q.pop(); 
		sum += (x + y); 
		q.push(x + y); 
	}
	cout << sum; 

}

 

1715번: 카드 정렬하기