[ 백준 1715 ] 카드 정렬하기 (C++) - 우선순위 큐

---

🔗 문제 링크

1715번: 카드 정렬하기

---

💡 문제 풀이 및 해석

1. 만약 카드의 숫자가 N개라면 반드시 N-1번의 계산을 해야 한다.
2. 여기서 가장 적은 수를 더해야 한다.
3. 항상 가장 작은 두 집합을 더해준다. 이러면 결과적으로 가장 작은 수가 나온다.
4. 만약, 큰 수가 들어가게 된다면, 그 수는 총 연산에서 이번 연산을 제외하고 반드시 한번 더 들어가야 하므로 최소값이 될 수 없다.

---

⭐️ 정답 코드 및 설명

#include <iostream>
#include <queue>

using namespace std;

int n;
priority_queue<int> q;

void input(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int num; cin >> num;
        q.push(-num);
    }
}

long sol(){
    long answer = 0;

    while(q.size() > 1){
        int num1 = -q.top(); q.pop();
        int num2 = -q.top(); q.pop();
        int num3 = num1 + num2;
        answer += num3;
        q.push(-num3);
    }

    return answer;
}
int main(){

    input();
    cout << sol();

    return 0;
}

---

🤔 문제 후기

딱히 어려운 점은 없었다.