1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
[난이도] Gold4
[유형] 우선순위큐
[풀이]
가장 작은 것부터 두개씩 뽑고, 두개의 합을 다시 큐에 넣으면 된다.
#include <cstdio>
#include <queue>
using namespace std;
int main(){
priority_queue<int> pq;
int N,a,ret=0;
scanf("%d",&N);
while(N--) scanf("%d",&a), pq.push(-a);
while(pq.size()>1){
int u,v;
u=pq.top(); pq.pop();
v=pq.top(); pq.pop();
ret+=-u-v;
pq.push(u+v);
}
printf("%d",ret);
}
github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1715.cpp