백준 1715 카드 정렬하기 (c++) : 피너클

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

1715번: 카드 정렬하기

그리드 문제다.

가장 효율적인 방법으로 모든 묶음을 하나의 묶음으로 만들어야한다.

묶음을 합칠때 합치는 두 묶음의 카드 수 만큼 비용이 든다. 그러니 카드 수가 적은 두 묶음을 하나로 합치는게 이득이다.

[10, 10, 10, 90] 이렇게 4개의 묶음이 있을때

10 + 10 -> 20 [10, 20, 90] 총 비용 : 20

10 + 20 -> 30 [30, 90] 총 비용 20 + 30 = 50

30 + 90 -> 120 [120] 총 비용 50 + 120 = 170

위 처럼 하는것이 가장 효율적이다

int n;
priority_queue<int> pq;

priority_queue를 이용한다. pq는 우선순위가 가장 높은 값이 top으로 오는 queue이다.

여기서 우선순위가 높은것은 값이 큰 숫자다. 100과 10이 있을때 100이 top으로 온다는 소리다.

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

그러니 값을 입력받고 -를 해 pq안에 집어넣는다. 100과 10을 입력받았을때 pq에는 -100과 -10이 들어가

-10이 top으로 가게 될것이다.

int sum = 0;
while (pq.size() > 1) {
	int a = -pq.top();
	pq.pop();
	int b = -pq.top();
	pq.pop();
	
	sum += (a + b);
	pq.push(-(a + b));
}
cout << sum << endl;

그다음에는 간단하다. while문을 만들고 만약 pq의 사이즈가 1보다 클때 반복문을 실행한다.

pq의 top의 값을 꺼내준다. 이때 -처리가 되어있으니 꺼내면서 -1을 곱해준다.

그로 pop한뒤 또 하나를 꺼내준다.

그리고 이 두개를 하나의 묶음으로 만들고 그 비용을 sum에 저장한뒤 묶음의 다시 pq에 저장한다.

위의 과정을 반복하면 sum에 총 비용이 저장된다.

#include <iostream>
#include <queue>

using namespace std;

int n;
priority_queue<int> pq;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		pq.push(-a);
	}
	int sum = 0;
	while (pq.size() > 1) {
		int a = -pq.top();
		pq.pop();
		int b = -pq.top();
		pq.pop();

		sum += (a + b);
		pq.push(-(a + b));
	}
	cout << sum << endl;
}

전체코드다.