[1715] 카드 정렬하기 (C++)

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N; cin >> N;
    int sum = 0;
    priority_queue<int, vector<int>, greater<int>> A;

    for (int i = 0; i < N; i++) {
        int tmp; cin >> tmp;
        A.push(tmp);
    }

    while (!A.empty()) {
        if (A.size() == 1) {
            break;
        }
        int n1 = A.top(); A.pop();
        int n2 = A.top(); A.pop();
        sum += n1 + n2;

        A.push(n1 + n2);
    }

    cout << sum;

    return 0;
}

 

* 단순 오름차순 정리 후 0 ~ N - 1항까지 차례대로 연산하면 반례가 발생한다

반례)

4 5 6 7 10

알고리즘 계산 : (5 + 6) + (5 + 6 + 7) + (5 + 6 + 7 + 10) = 11 + 18 + 28 = 57

논리적인 계산 : (5 + 6) + (7 + 10) + (5 + 6 + 7 + 10) = 11 + 17 + 28 = 56

따라서 우선순위 큐를 사용하여 연산이 발생할 때 마다 재정렬 될 수 있도록 한다

 

1. 우선순위 큐를 생성, 오름차순으로 정리

2. 가장 작은 수 n1, n2를 더한 값을 sum에 더한다

3. A의 크기가 1이 되면 반복문 탈출

4. sum 출력