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

문제링크: https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

문제 접근에 대해서 이해하면 쉽게 구현한 문제이다.

 

우선, 그리디한 방식으로 문제를 도출할 수 있다는 것을 이해해야 한다!

 

접근방식

 

1. 생각해보면, 항상 작은수를 먼저 처리해주면 최소값이 도출이 된다는 것을 알수 있다.

 

2. 그렇다면 새로 추가되는 수는 어떻게 관리해주어야 할까? 

새로 수를 넣어줄때 마다 정렬을 해야하나? 

 

아니다!

 

그냥 편하게 우선순위 큐를 사용하면 될 일이다. 

자동으로 lgn번의 탐색으로 수를 정렬된 상태로 보관해주기 때문에

해당 문제에 가장 적합한 자료구조이다.

 

 

문제풀이 

 

1.  구현 자체는 너무나도 단순하다.

priority_queue를 사용하여 문제를 해결하자.

 

정답코드입니다.

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

int n = 0;
priority_queue <int> que;
long long result = 0;

int main() {
	cin >> n;

	int temp;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		que.push(temp * -1);
	}

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

		int a = que.top() * -1;
		que.pop();
		int b = que.top() * -1;
		que.pop();

		result += (a + b);

		que.push( (a + b) * -1);


	}

	cout << result << endl;
	return 0;
}