algospot STRJOIN 문자열 합치기

문제

https://algospot.com/judge/problem/read/STRJOIN

걸린 시간

00 : 22 : 58

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, tmp;
        cin >> n;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = 0; i < n; i++){
            cin >> tmp;
            pq.push(tmp);
        }
        int ans = 0;
        while(pq.size() > 1){
            int s1 = pq.top();
            pq.pop();
            int s2 = pq.top();
            pq.pop();
            ans += s1+s2;
            pq.push(s1+s2);
        }
        cout << ans << "\n";
    }
    return 0;
}

종만북 10장 탐욕법에서 준비한 예제를 풀어보았다.

난이도가 쉬워서인지 문제의 접근이 매우 직관적이여서 정당성 증명 부분을 건너뛰고 그대로 구현했다.

책에선 어려운 문제일수록 여러개의 탐욕적 선택이 존재할 수 있고 직관적이지 않은 경우도 많기 때문에 정당성을 증명하는 과정을 빼먹지 않고 연습하는 것이 좋다고 했다.