백준 1715 : 카드 정렬하기

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

1. 접근

• 가장 작은 숫자들을 계속해서 2개씩 더해주면 된다.
  => 앞의 두 값을 더해주고, 그 값들을 정렬해서 다시 작은 값 2개를 더해주면 된다!
• 반복문을 사용해서 값이 2개보다 적어질 때까지 계속해서 더해주고, 한번 시행시마다 정렬을 진행해보았다
  => 시간초과가 나왔다.. N이 10만까지이니 당연한 결과
• 작은 값들을 더해준다는 기본적인 알고리즘은 더이상 효율적으로 구할 수 없다. 정렬을 하지 않아도 되는 자료구조를 찾아야 한다.
  => Priority_Queue : 값을 push하면 자동으로 정렬되어, 정렬 순서에 가장 부합하는 값을 top 값으로 갖게 된다

2. 나의 풀이

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

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

	int n;
	priority_queue<int,vector<int>,greater<int>> cards;

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

	if (n == 1) {
		cout << 0<<"\n";
		return 0;
	}

	int ret = 0;
	while (cards.size() > 1) {
		int sum = 0;
		sum += cards.top();
		cards.pop();
		sum += cards.top();
		cards.pop();
		ret += sum;

		cards.push(sum);
	}
	cout << ret << "\n";

	return 0;
}