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

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

1715번: 카드 정렬하기

 

우선수위 큐와 그리디 문제다.

 

처음에는 작은 수가 여러 번 더해지는 게 최솟값이 나올 거라고 생각해

정렬 후 각 수에 n - i를 곱해서 더하는 방법을 생각했다.

이 방법은 항상 앞의 두 수 합에 바로 뒤에 숫자를 더한다.

반례가 있을 것 같다는 생각이 들었다. (a + b) (c + d) e 를 더하는 것이 최솟값이 나오는 경우가 있을 것 같았다.

있었다.

 

원소 삽입마다 정렬이 되는 우선순위 큐를 이용했다.

priority_queue는 기본 값이 내림차순이므로 오름차순으로 설정했다.

top()으로 앞에 두 수를 빼내고 합을 우선순위 큐에 삽입하는 방식이다.

삽입하면서 그 값들을 더해주고 큐의 사이즈가 1이 될 때까지 반복한다.

 

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

// 오름차순 우선순위 큐
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, sum = 0;	cin >> n;

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

	// 큐의 사이즈가 1이면, 카드가 한 묶음이면 종료
	while (pq.size() > 1) {
		int one = pq.top();	pq.pop();
		int two = pq.top();	pq.pop();
		pq.push(one + two);
		sum += one + two;
	}

	cout << sum;
}

(✿◕‿◕✿)