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

 

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

 

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

1715번: 카드 정렬하기

---

 

해결전략

 

탐욕법, Greedy 그리디 알고리즘

 

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

• priority_queue는 기본적으로 내림차순 정렬(큰 수부터 차례대로 나오는 정렬)이다.
• priority_queue<int, vector<int>, greater<int> > 선언을 하면  오름차순 정렬(작은 수부터 차례대로 나오는 정렬)로 바꿀 수 있다.

 

---

 

코드

 

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

int n;
priority_queue<int, vector<int>, greater<int> > pQ;
vector<int> dp;

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

	cin >> n;
	dp.resize(n);
	int input;
	for (int i = 0; i < n; i++) { 
		cin >> input;
		pQ.push(input);
	}

	if (n == 1) {
		cout << "0" << "\n";
		return 0;
	}
	else if (n == 2) { // 숫자가 두 개일 경우, 두 숫자의 합을 출력 후 종료
		int tmp = pQ.top();
		pQ.pop();
		cout << tmp + pQ.top() << "\n";
		return 0;
	}

	dp[0] = pQ.top();
	pQ.pop();
	dp[1] = dp[0] + pQ.top();
	pQ.pop();
	pQ.push(dp[1]);
    
	int sum = dp[1];
    
	for (int i = 2; i < n; i++) {
		dp[i] = pQ.top();	// 가장 작은 숫자를 dp에 저장하고, 큐에서 제거
		pQ.pop();
		dp[i] += pQ.top();	// 두 번째 숫자와 첫 번째 숫자의 합을 dp에 저장하고, 큐에서 제거
		pQ.pop();
		pQ.push(dp[i]); 	// 두 숫자의 합을 다시 큐에 넣음
		sum += dp[i];		// 합계에 더함
	}

	//for (int i = 0; i < dp.size(); i++){
	//	cout << dp[i] << " ";
	//}
	//cout << "\n";
	//cout << "sum = " << sum << "\n";
	//cout << "\n";

	cout << sum << "\n";

	return 0;
}

 

처음에는 vector와 deque를 사용해서 sort를 했지만 시간초과가 나왔다.

그래서 priority_queue를 사용하니 시간복잡도가 줄어 통과됐다.

참고로 vector와 deque의 sort 정렬 시간복잡도는 O(n)이고 priority_queue는 O(log n)이다.

---