[1715] 카드 정렬하기 - 우선 순위 큐 ★☆☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

---

[ 문제 접근 ]

 

우선 정렬하고 앞에서부터 하나씩 더해 나가면 될거라고 판단해서 그대로 구현했다가 틀렸다.

 

그러고 생각해보니  30  40  50  60  <-  내 코드의 반례가 된다.

 

30과 40을 더했을 때 나오는 70을 남은 수 50 과 60과 비교하여 작은 수부터 더해줘야하는것이다.

 

이 경우, 우선순위 큐를 사용하여 자동으로 정렬되게끔 하면 해결된다.

---

[ 처음 코드 ]

 

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>


using std::cout; using std::cin;
using std::vector; using std::string;


int N;
int card[100001];
vector<int> answer;
int real_answer;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> card[i];
	}
	std::sort(card, card + N);

	int temp = card[0];
	for (int i = 1; i < N; i++) {
		temp += card[i];
		answer.push_back(temp);
	}

	for (auto& elem : answer)real_answer += elem;

	cout << real_answer;
	return 0;
}

 

---

[ 최종 코드 ]

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>


using std::cout; using std::cin;
using std::vector;

int N;
std::priority_queue<int,vector<int>,std::greater<int>> pq;

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

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

	
	while (pq.size() != 1) {

		int x = pq.top();  // 첫번째
		pq.pop();

		int y = pq.top();  // 두번째
		pq.pop();

		answer += (x + y);
		pq.push(x + y);
	}
	
	cout << answer;
	
	return 0;
}

 

---