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

 

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

int main() {
	//테스트 케이스 입력받기
	int n;
	cin >> n;

	//총 계산횟수 구하는 변수
	int total_cnt = 0;

	//우선순위 큐를 오름차순으로 저장
	priority_queue<int, vector<int>, greater<int>> pq;

	//카드 더미수 입력받고 우선순위 큐에 저장
	while (n--) {
		int input;
		cin >> input;
		pq.push(input);
	}

	//큐 안에 저장된 원소가 1개가 될 때까지
	//가장 적은 수를 가진 더미 2개를 뽑아 더해서 다시 더미에 넣고
	//합 한 수는 총 계산 횟수에 업데이트 해줌
	while (pq.size() != 1) {
		int input1, input2;
		input1 = pq.top();
		pq.pop();
		input2 = pq.top();
		pq.pop();

		int hap = input1 + input2;
		pq.push(hap);

		total_cnt = total_cnt + hap;
	}

	cout << total_cnt;
}