[ 백준 / C++ ] 1715 : 카드 정렬하기

[ 문제 ]

 

1715번: 카드 정렬하기 (acmicpc.net)

 

[ 접근방법 ]

 

모든 카드를 우선순위 큐에 넣고 제일 작은 두 카드를 꺼낸다.

 

두 카드의 합을 저장하고 우선순위 큐에 넣은 후, 위 과정을 반복한다.

 

각 과정은 O(log n) 이므로, 시간복잡도는 결국  O(n log n) 이다.

 

[ 소스코드 ]

 

#include <iostream>
#include <queue>

using namespace std;

int n, cnt, ans;
priority_queue<int, vector<int>, greater<int>> pq;

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

    cin >> n;

    while (n--)
    {
        cin >> cnt;
        pq.push(cnt);
    }

    while (pq.size() > 1)
    {
        cnt = pq.top();
        pq.pop();
        cnt += pq.top();
        pq.pop();
        ans += cnt;
        pq.push(cnt);
    }

    cout << ans;

    return 0;
}