백준 1715번 카드 정렬하기 (C++)

 우선순위 큐라는 분류를 보지않았다면 조금 해맸을 것 같다. 주어진 카드뭉치를 우선순위 큐 오름차순으로 정리하고 꺼내면서 연산하면 된다.

그러나 처음 이해한 것이 예를들어 N =3 이고 A B C라 정렬되어있다하면

(A + B) + (A + B + C) 인줄 알았다.  그래서 꺼내면서 중복처리해주면서 연산했는데 이런문제가 아니었다. 로직은 다음과 같다.

1. 두개를 꺼내 더함

2. 더한 값을 큐에 다시 넣음

3. 더한 값을 answer에 sum 해놓음

3. 1,2,3번을 큐가 빌때까지 반복, 단 큐가 끝날 때 아직 더하지 않은 요소가 있다면 덧셈함.

 

문제를 확실히 읽고 파악하는 연습이 필요하다.

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

priority_queue<int, vector<int>, greater<int>> q;

int main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		q.push(tmp);
	}

	int answer = 0;
	int cnt = 0;
	int sum = 0;
	while (!q.empty()) {
		cnt++;
		int x = q.top();
		q.pop();
		sum += x;
		if (cnt == 2) {	
			answer += sum;
			q.push(sum);
			sum = 0;
			cnt = 0;
		}
	}
	cout << answer << '\n';
}