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

문제링크 : https://www.acmicpc.net/problem/1715

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
int arr[100001];

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    int tmp, answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;

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

    while(!pq.empty())
    {
        int sum = 0;
        sum += pq.top(); //합칠 첫번째 수
        pq.pop();
        if(!pq.empty())
        {
            sum += pq.top();//합칠 두번째 수
            pq.pop();
            if(!pq.empty()) pq.push(sum); //합칠 수가 남아있다면 푸쉬쉬
        }
        answer += sum;
    }

    if(N==1) answer = 0;
    cout << answer;

    return 0;
}

 

pq를 사용하여 간단하게 풀이가 가능한 문제이다.

 

최소한의 비교를 위해 작은 값부터 누적하여 더해주며, 이때 pq를 활용한다.

합칠 수를 체크하기 위해 우선 첫 번째 pq의 top을 합에 합쳐주며, 만약 합칠 두 번째 수가 남아있다면 이어서 누적합을 구해주고 기존 pq는 삭제한다.

이 상태에서 추가적으로 합칠 수가 남아있다면 현재 누적합을 pq에 담아주고, 위 과정을 반복하여 최종 누적합을 구한다.

 

주의할 점은 n=1일 때는 비교가 필요없으므로 예외처리가 필요하다.