백준 1715번: 카드 정렬하기

 

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

1715번: 카드 정렬하기

 

키워드 - 힙, 구현, 우선순위큐

 

Approach

정수 10 20 40 이 입력으로 들어오고 큐에 쌓이는 순서는 10 20 40

최상위 두개의 값을 pop 을 하여 10 + 20 덧셈을 다시 큐에 넣으면 30, 40

 

다음 상태에서 30 + 40 = 70 

 

총 비교회수는 100(30 + 70) 이 된다.

 

Source

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <math.h>
#include <memory.h>
using namespace std;

#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
#define ll long long

int main() {

    cin.tie(0);
    std::ios::sync_with_stdio(false);

    int n; cin >> n;

    priority_queue<int, vector<int>, greater<int> > q;
    while (n--) {
        int d; cin >> d;
        q.push(d);
        // 순차적으로 모두 넣어줌
    }

    int sol = 0;
    while (q.size() > 1) {
        int a = q.top(); q.pop();
        int b = q.top(); q.pop();
        sol += a + b;
        q.push(a + b);
    }

    cout << sol << CENDL;

    return 0;
}
​