백준 g4 1715 카드 정렬하기 c++

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

1715번: 카드 정렬하기

 

문제

정렬된 카드 묶음 A, B가 있을 때 두 묶음을 합치는 방법은 (A + B)번 비교하는 것이다.

N개의 카드 묶음이 있을 때, 최소 몇 번 비교해서 합칠 수 있는지 구하기

 

풀이

예를 들어 10 20 30 50이 있다고 하면

 

(10 + 20) > (30 + 30) -> (50 + 60) 이런 식으로 계산을 하게 된다.

앞에서 더해진 A+B의 합이 계속해서 다른 카드 묶음과 비교되기 때문에, A+B의 합은 작을 수록 좋다. 왜냐하면 계속해서 겹쳐져서 또 더해지는 부분이기 때문이다.

 

또, A+B 더해진 묶음이 다른 묶음보다 클 수도 작을 수도 있으므로 결국 순서는 A+B로 새로운 카드 묶음이 생길 때마다 정렬해주어야 한다.

매 순간마다 최소1, 최소2의 합을 구해주면 된다.

 

이에 적합한 자료구조는 삽입과 삭제가 용이하고, 최소 최댓값을 쉽게 구할 수 있는 set이나 pq정도가 있겠다. set은 시간이 오래 걸리는 lgN이고, 굳이 이전 or 다음 원소를 구할 필요가 없으므로 priority queue로 구현을 해주었다.

 

min heap은 다음과 같이 코드를 작성해주면 된다.

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

 

전체 코드

/*boj g4 1715 카드 정렬하기*/
#include <iostream>
#include <queue>

using namespace std;

int N;
priority_queue<int, vector<int>, greater<int>> pq;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    while (N--) {
        int x;
        cin >> x;
        pq.push(x);
    }
    int ans = 0;
    while (pq.size() != 1) {
        int x1 = pq.top();
        pq.pop();
        int x2 = pq.top();
        pq.pop();

        ans += (x1 + x2);
        pq.push(x1 + x2);
    }

    cout << ans << "\n";
}