백준 1715 (카드 정렬하기) / C++

문제 링크 : 1715번: 카드 정렬하기 (acmicpc.net)

1715번: 카드 정렬하기

>풀이

 

카드 묶음 중 가장 작은 두 개를 골라 합친다 -> 합친 두 카드를 카드 묶음에 넣는다 -> 반복

 

가장 작은 두개를 고르기 위해 정렬을 계속해서 반복해야 한다. 따라서 힙을 사용한 우선순위 큐를 써서 문제를 풀자

 

#include <bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>, greater<int> > pq;
int N;

int main(void)
{
        int n;
        int sum = 0;

        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
              scanf("%d", &n);
              pq.push(n);  
        }

        while(pq.size() > 1) {
                int n1, n2;

                n1 = pq.top(), pq.pop();
                n2 = pq.top(), pq.pop();
                sum += (n1 + n2);
                pq.push(n1 + n2);
        }

        printf("%d", sum);
        return 0;
}