[BOJ 백준] 1715번 카드 정렬하기

문제

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

1715번: 카드 정렬하기

접근

카드를 합칠 때 적은 수의 카드 묶음을 합쳐나가는 방식이 최소 비교 횟수이다. 따라서 오름차순으로 정렬된 우선순위 큐에 카드 묶음들을 넣어준 다음 top에 있는 두 카드 묶음을 합쳐주면 자연스레 작은 수의 카드 묶음을 더해나갈 수 있다. 이때 두 개의 카드 묶음을 합쳐서 만들어지는 새로운 카드 묶음을 다시 큐에 넣어주는 것을 잊지 말자. 이렇게 진행하다 보면 모든 카드가 합쳐져서 큐의 size가 1이 되는 시점이 오면 while문을 종료하고 답을 출력해준다.

 

코드

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int n, temp, answer = 0;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        pq.push(temp);
    }
    while (pq.size() != 1) {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        answer += a + b;
        pq.push(a + b);
    }
    cout << answer;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study