백준 1715. 카드 정렬하기 (우선순위큐)

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

1715번: 카드 정렬하기

문제가 솔직히 제대로 이해되지 않아, 그냥 일단 구현했다. 

문제에서 인풋으로 10, 20, 30, 40을 넣으면 100이라는 출력값을 원하는 것 같은데, 

문제 조건으로 답을 생각해보면 190이었다. 그래서 나는 190을 만드는 방법으로 구현했는데,,, 맞았다. 

 

1. 특징 

1) 그리디

2) 우선순위큐

 

2. 구현 포인트

1) 그리디: 제일 작은값과 그 다음 작은값을 골라서, 합친다 -> 합친 것을 다시 책상에 놓는다. 

이를 n-1번 반복한다. 

2) 우선순위큐: 제일 작은값, 그리고 그 다음 작은값이 필요하며, push와 pop이 자주 일어나서, 우선순위큐를 사용했다.

이진검색트리(multiset)를 사용해도 논리적으로 가능하지만, 우선순위큐가 더 빠르다. (이진검색트리로는 시간초과가 날수도있다.) 

 

3. 코드

#include <iostream>
#include <queue>
using namespace std;

int n;
int x;
int ans;
int nv;
int main()
{       
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> _pq; //최소힙
    int tn = n-1;
    while(n--)
    {
        cin >> x;
        _pq.push(x);
    }

    while(tn--)
    {
        nv = _pq.top();
        _pq.pop();
        nv+= _pq.top();
        _pq.pop();
        ans += nv;
        _pq.push(nv);
    }
    cout << ans;
}