[알고리즘] 카드 정렬하기

구현 방식

• 처음에는 간단하게 정렬해놓고, 앞에서부터 차례차례 합쳐나가면 되지 않을까 싶었다.
• 하지만 아래와 같은 경우에는 최대값을 내놓지 못한다.

4
30
40
50
60
# 답 : 360

• 30과 40을 더한 후에 70 이 되는데, 70 + 50 보다 60 + 50 이 더 싼 값에 합칠 수 있기 때문!
• 그러므로, 합친 카드 그룹을 계속적으로 우선 순위 큐에 넣어주면서 두개를 뽑아서 계산해나가야한다.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int N;
	cin >> N;
	priority_queue<int,vector<int>,greater<int>> pq;
	int cards;
	while (N--)
	{
		cin >> cards;
		pq.push(cards);
	}

	solution(pq);
	return 0;
}

void solution(priority_queue<int, vector<int>, greater<int>>& pq)
{
	// 두개를 합쳐서 나온 카드 그룹도
	// pq 에 추가하면서 계산
	int result = 0;
	int c1, c2;
	while (2 <= pq.size())
	{
		c1 = pq.top(); pq.pop();
		c2 = pq.top(); pq.pop();
		result += (c1 + c2);
		pq.push(c1 + c2);
	}

	cout << result;

}