[Gold 4] 1715 카드 정렬하기

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

이문제는 greedy 알고리즘을 활용해서 해결해야한다.

 

가장 적은 비교 횟수를 통해 카드를 정렬하기 위해서는 가장 작은 카드 뭉치들을 사용해서 값을 누적해야한다.

가장 작은 카드 2장을 뽑기 위해서는 배열을 정렬해서 카드를 뽑으면 된다.

 

처음 시도한 방법은 vector에 값을 담은 후 sort하여 카드를 뽑아 값을 누적하였다.

이러한 방법은 처음 뽑은 2장의 카드의 합이 이후에 뽑을 카드보다 작은 경우 성립하는 방법이다.

 

즉, 뽑아야하는 2장의 카드가 계속해서 작아야한다는 문제가 생긴다.

이러한 문제는 우선순위 큐를 사용하면 해결할 수 있다.

계속해서 sort 함수를 이용해 배열을 정렬하게 된다면 실행 시간을 over할 가능성이 생긴다.

 

우선순위 큐를 사용해서 가장 top에 있는 카드 2장을 뽑은 후 누적한다. 이후 뽑은 카드 2장의 합을 우선순위 큐에 삽입한다.

이러한 연산을 큐의 요소의 계수가 1개가 될 때 까지 반복하면 문제를 해결할 수 있다.

 

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

int N;
int value = 0;
priority_queue<int, vector<int>, greater<int>> q;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	int input;
	for (int i = 0; i < N; i++) {
		cin >> input;
		q.push(input);
	}
	
	while (q.size() > 1) {
		int n1 = q.top();
		q.pop();
		int n2 = q.top();
		q.pop();
		value += n1 + n2;
		q.push(n1+n2);
	}
	cout << value << '\n';
}