정렬을 통해 해결하는 문제로 생각했는데 문제를 정확히 이해하지 못했다. 문제 에서 설명하기에는 현재 10과 20을 합친 값은 30으로 기존 40보다 작으니 문제가 되지 않았는데 히든 케이스를 보면 합친 값이 기존 값보다 작은 경우 재 정렬을 통해 카드를 합쳐야 했다.

맨 처음만 정렬을 한 기존 코드는 오답이고 새롭게 매번 카드 묶음을 계산할때마다 정렬하기 위해 Priority queue(우선 순위 큐)를 이용하였고 Top이 가장 작아야 하기 때문에 오름 차순으로 만들어주었다.

그리고 입력 값인 N이 1부터 주어지는데 문제는 최소 "두 카드 묶음" 부터 시작하기에 N이 만약 1이 입력된다면 오답 처리된다.

오답

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>

using namespace std;
int n,a;

//top이 가장 작길 원함 (오름 차순)
priority_queue<int,vector<int>,greater<int>> q;
int result[100001];
int tmp;

int main() {

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        q.push(a);
    }

    while (q.size() != 1) {
        tmp += q.top();
        q.pop();
        tmp += q.top();
        q.pop();
        q.push(tmp);
    }

    cout << q.top();

    return 0;
}

정답

# #include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>

using namespace std;
int n,a;

//top이 가장 작길 원함 (오름 차순)
priority_queue<int,vector<int>,greater<int>> q;
int result;
int tmp;

int main() {

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        q.push(a);
    }

    if (n == 1) {
        cout << 0;
        return 0;
    }

    while (!q.empty()) {
        tmp = 0;
        tmp += q.top();
        q.pop();
        if (!q.empty()) {
            tmp += q.top();
            q.pop();
            if (!q.empty()) {
                q.push(tmp);
            }
        }
        result += tmp;
        
    }

    cout << result;

    return 0;
}