STRJOIN (하, p. 380)

문제#

어떻게 풀었나?#

앞쪽에 더한 숫자는 계속해서 누적되므로, 앞에 더하는 숫자일수록 가장 작은 숫자여야 된다고 생각했다. 어차피 합치는 횟수는 변하지 않으므로, 가장 작은 숫자 2개씩만 뽑아서 더하면 되는 것이다. 구현은 priority_queue(Min Heap)를 써서 구현했다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int>> mnh;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n; cin >> n;
        for(int i=0; i<n; i++) {
            int x; cin >> x;
            mnh.push(x);
        }
        int ans=0;
        while(mnh.size()>=2) {
            int x = mnh.top(); mnh.pop();
            int y = mnh.top(); mnh.pop();
            mnh.push(x+y);
            ans += (x+y);
        }
        printf("%d\n", ans);
        while(!mnh.empty()) mnh.pop();
    }
    return 0;
}

Comment#

난이도 ‘중’의 문제는 아닌 듯 하다. ‘하’로 변경함.