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

https://www.acmicpc.net/problem/1715

이 문제는 어떻게 카드를 합쳐 나갈 때 비교 횟수가 적어지는지 파악하는 그리디 알고리즘 문제라고 볼 수 있다. 정말 쉽게 생각하면 방법은 매우 간단합니다. 가장 작은 수의 카드 묶음을 더 해나간다면 자연스럽게 제일 비교 횟수가 적은 방법을 찾게 됩니다.

EX1)

30 50 100 300 320

30+50 sum = 80

80 100 300 320

80+100 sum= 80+180

180 300 320

180+300 sum= 80+180 + 480

320 480

320+480 sum= 80+ 180 + 480 + 800 (가장 비교 횟수가 적은경우)

800

EX2)

10 20 40

10+20 sum = 30;

30 40

70 sum = 30+70; (가장 비교 횟수가 적은경우)

위 예시를 참고해서 코드를 구현하면 다음과 같습니다.

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


priority_queue<int,vector<int>,greater<int>> pq;

int main() {
  
    int n;
    cin >> n;
    int num;
    long long sum = 0;
    while (n--)
    {
        cin >> num;
        pq.push(num);
    }

    if (n == 1)
    {
        cout << pq.top() << '\n';
    }
    else
    {
        while (pq.size() != 1)
        {
            int n1, n2;
            n1 = pq.top();
            pq.pop();
            n2 = pq.top();
            pq.pop();
            pq.push(n1 + n2);
            sum = sum + n1 + n2;
        }
    }
    cout << sum << '\n';
}