[C++] 백준 1715 카드 정렬하기

1. 문제 

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

 

2. 풀이과정

카드 묶음을 합쳐가면서 비교를 수행하는데 최소의 비교로 합친다면 최소 몇번의 비교가 필요한지 묻는 문제
즉, 우리는 "현재 존재하는 카드 묶음 중에서, 가장 적은 2개의 묶음을 우선적으로 계산" 하는 것이 정답이라는 것을 파악했습니다.
ex) 5 4 3 2 1 카드 묶음이 이렇게 구성되어 있다면
(1+2) + (3+3) + (6+4 )+ (10+5) <= 이게 가장 최소의 비교로 합치는 경우입니다.
이전 카드 묶음의 비교횟수가 다음 카드 비교횟수에 영향을 주기 때문에 가장 적은 카드 묶음을 계속 합쳐야합니다!!

✏ 알고리즘

N개의 카드 묶음에서 가장 작은 두 개를 골라 합친다 -> 합친 두 카드를 카드 묶음에 넣는다 -> 반복
N개의 카드 묶음에서 최소값 2개를 꺼내기 위해 사용한 것이 최소힙이다.
이때 우선순위 큐를 사용해서 최소 힙을 사용했다.


1. 카드 묶음들을 우선순위 큐에 들어있다. pop을 2번해서 가장 적은 묶음 2개를 빼준다.

2. 이 두 묶음을 더하여 다시 우선순위 큐에 push해준다.

3. 두 묶음의 합이 두 묶음의 비교횟수 이므로 result에 더해주고 다시 1번 과정으로 돌아간다.

4. 힙에 1개의 값이 남을 때 까지 위 1 ~ 3 과정을 반복한다. (2개가 나와서 1개가 다시 들어가니 언젠가 1개가 남음)

5. 반복이 끝났을때 result의 값이 답이다.

 

🤔우선순위 큐

우선순위 큐는 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조
우선순위 큐는 힙을 사용하여 구현하는 것이 가장 효율적입니다.

(최소)힙은 완전 이진 트리 구조로 부모노드는 자식노드보다 반드시 값이 작은 구조를 유지하며 데이터를 저장합니다.
합니다.
따라서 값을 힙에 저장하면 루트(최상위)노드는 제일 작은 값이 됩니다.
pop을 하면 이 최상위 노드가 꺼내지고 다음 최솟값이 최상위노드로 가면서 트리가 다시 정렬? 채워지게 됩니다.
최대힙은 부모노드 > 자식노드를 유지하면서 저장

최대 힙과 최소 힙 그림

push 시에는 해당 값이 적절한 위치의 노드로 가야하기 때문에 시작복잡도 O(log N)
pop 시에는 루트노드가 빠지고 그 위치로 다음 값이 채워져야하기 때문에 시간복잡도 O(log N)

3. C++ 정답코드

#include <iostream>
#include <queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);    cin.tie(NULL);

    priority_queue <int, vector<int>, greater<int>> pq; //최소 힙으로 우선순위 큐 선언 
    int n; 
    cin >> n;
    for (int i = 0; i < n; i++) //우선순위 큐에 다 넣음
    {
        int x;
        cin >> x;
        pq.push(x);
    }
    int result = 0;
    while(pq.size() > 1) //우선순위 큐에 값이 하나만 남을 때 까지 반복
    {
        // 우선순위 큐에서 가장 작은 두 수를 꺼내서 합침
        int a = pq.top();
        pq.pop();                                                                                   
        int b = pq.top();
        pq.pop();
        int sum = a + b; 
        pq.push(sum);  // 합친 결과를 우선순위 큐에 다시 넣음 
        
        result += sum;  // 결과값을 누적
    }
    cout << result;
    return 0;
}