https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
이 문제의 경우 생각하는건 쉬웠다 사실 어떠한 배열에서 가장 작은 2개를 선택한 후 이를 그다음 작은애랑 더해주면 되는 문제였다 그래서 이문제를 나는 큐를 사용해서 풀고 싶었다. priority queue를 사용해서 풀고 싶었기 때문에 사실 데큐를 사용해서 풀수도 있는 문제기는 하다 데큐로 푸는 방식은 그냥 입력받은애들을 작은애들 순으로 소팅한 후 더한후 front에 넣고 다시 front에서 두개를 더한후 넣고 다시 두개 팝해서 넣고 하는 방식으로 하면 된다 이러한 로직도 priority queue에 적용이 되기 때문에 사용하면 된다 소스코드는 이렇게 된다
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
int main() {
int card;
int n;
int sum = 0;
cin >> card;
for (int i = 0; i < card; i++) {
cin >> n;
pq.push(n);
}
while (pq.size() > 1) {
int x, y;
x = pq.top();
pq.pop();
y = pq.top();
pq.pop();
sum += (x + y);
pq.push(x + y);
}
cout << sum;
}