[C++] 백준 온라인 저지 1715번 카드 정렬하기 풀이

N개의 숫자 묶음이 주어질 때 숫자 묶음들을 비교하려면 최소 몇 번만 비교하면 되는지 구하는 문제 

 

---

문제의 조건

 

1. 정렬된 두 숫자 묶음이 있다. 두 묶음을 각각 A, B라 하면 두 묶음을 비교하는데 필요한 횟수는 A+B번이다. 

 

2. 10장, 20장, 40장 처럼 2개보다 많은 숫자 묶음이 있을 때 2개씩 골라서 비교를 하는데 묶음들을 고르는 순서에 따라서 횟수가 달라진다.

 10장과 20장을 먼저 합친 뒤(10+20=30), 남은 40장을 합치는 경우의 수를 더했을 때 (10+20)+(30+40)=100 총 100번의 비교가 필요하다. 

 하지만 10장과 40장을 합친 뒤(10+40=50), 남은 20장을 합치는 경우를 더하면 (10+40)+(50+20)=120 총 120번의 비교가 필요해서 100번보다는 비효율적이다. 

 단순히 누적합계를 구하는 문제가 아닌 앞전에 2개를 더했던 횟수에 새롭게 2개를 더한 횟수를 더해가며 최종 비교 횟수를 구해야 한다. 

 

3. 숫자 묶음들이 주어졌을 때 최소 비교 횟수를 구해서 출력하기 

 

 

풀이 과정

 

 처음엔 오름차순으로 정렬한 후 더하는 방향으로 코드를 짰는데 실패해서... 구글링 후에 새로운 힌트를 얻어서 코드를 짰습니다. 

 

1. 보기에서 알 수 있듯이 큰 수보다는 작은 수끼리 먼저 더하는 것이 이득이다. 

 

2. 우선순위 큐를 이용해서 최소힙을 구성한다. 최소힙의 첫번째, 두번째 원소들을 꺼내서 더한 후 정답에 더한다. 방금 구한 값을 또 우선순위 큐에 추가한다. 그러면 큐의 갯수가 점점 하나씩 줄어들 것임. 큐에 원소가 하나만 남을 때까지 반복한다. 

 

 

코드

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    priority_queue<int, vector<int>, greater<int>> minHeap; //최소힙
    for (int i = 0; N > i; i++)
    {
        int n;
        cin >> n;
        minHeap.emplace(n);
    }
    
    long answer = 0;
    while (1 < minHeap.size())
    {
        int a = minHeap.top(); //현재 묶음 중 가장 작은 2개 꺼내서 더하기 
        minHeap.pop();
        int b = minHeap.top();
        minHeap.pop();
        answer += a + b; //정답에 경우의 수 누적합계 구하기 
        minHeap.emplace(a + b); //아까 더한 값을 다시 큐에 추가 
    }
    
    cout << answer;
    
    return 0;
}