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

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

1715번: 카드 정렬하기

 

 

우선순위 큐를 이용하여 푸는 문제이다.

 

풀이 순서는 다음과 같다.

처음에, 최소 힙을 사용해서 입력받은 데이터를 모두 push한다.

그 다음에, 사이즈가 1이 될 때까지 다음을 반복한다.

1. 최소 힙에서 두 개를 꺼낸다.

2. 두 개를 더한 결과를 cnt에 추가한다.

3. 두 개를 더한 결과를 최소 힙에 push한다.

 

이 문제는 사실 python으로 풀이해도 되지만, (python : min-heap) c++로 푸는 것에 재미가 들려서 c++로 풀이하였다.

 

C++ : max-heap Python: min-heap

우선순위 큐 : 삽입/삭제 -> 시간복잡도 O(logN)

 

소스코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq; // minHeap
    while(n--) {
        int num;
        cin >> num;
        pq.push(num);
    }
    int cnt = 0;
    while (pq.size() != 1) {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        cnt += a + b;
        pq.push(a + b);
    }
    cout << cnt;

    return 0;
}

 

채점 결과