카드 정렬하기 (feat. 백준, 1715번)

카드 정렬하기
https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, ans = 0;
    priority_queue<int, vector<int>, greater<int>> q;
    cin >> N;
    for(register int n = 0, v; n < N; ++n)
        cin >> v, q.push(v);
    while(1){
        if(q.size() < 2)
            break;
        register int A = q.top(); q.pop();
        register int B = q.top(); q.pop();
        ans += A + B, q.push(A + B);
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

1. 입력된 값중 가장 작은 값과 그 다음으로 작은 값을 더하는 과정이 반복되었을때, 문제가 원하는 최소값을 도출할 수 있습니다.
2. 따라서 오름차순 우선순위큐에 입력값을 넣고 가장 작은 2개의 값을 뽑아 더한 뒤, 다시 큐에 넣는 방식으로 해답을 구했습니다.