카드 정렬하기

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

1715번: 카드 정렬하기

 

카드의 장수가 적은 카드 묶음끼리

더하는 것이 횟수를 줄일 수 있다.

 

10, 20, 40이 있으면

10, 20을 합치고 

30, 40을 하면 -> 100회

 

즉, 현재 존재하는 카드 묶음 중에서

가장 적은 2개의 묶음을 우선적으로 계산

-> 우선 순위 큐

 

<우선순위 큐 구현>

배열을 이용한 이진트리로 구현한다.

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int genzai;
 
int arr[100'004];
int Heap[100'004];
 
// 최소 힙
void Heap_push(int data)
{
    int idx = ++genzai;
    Heap[idx] = data;
 
    while ((idx != 1) && (data < Heap[idx / 2]))
    {
        swap(Heap[idx], Heap[idx / 2]);
        idx = idx / 2;
    }
}
 
int Heap_pop()
{
    // 완전 이진 트리 -> 1부터 시작
    int result = Heap[1];
 
    // 제일 마지막을 위로 올리고
    // Top-down
    Heap[1] = Heap[genzai];
    genzai--;
 
    int parent = 1;
    int child;
 
    while(true)
    {
        child = parent * 2;
        // 자식노드 두 개 중 작은 값을 선택
        if (child + 1 <= genzai && Heap[child + 1] < Heap[child])
            child++;
 
        // 부모가 자식보다 작으면 끝
        if (child > genzai || Heap[parent] < Heap[child])
            break;
 
        swap(Heap[child], Heap[parent]);
        parent = child;
    }
 
    return result;
}
 
int main()
{
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    int ans = 0;
    int cmp_cnt = n - 1;
 
    for (int i = 0; i < n; i++)
        Heap_push(arr[i]);
 
    for (int i = 0; i < cmp_cnt; i++)
    {
        int n1 = Heap_pop();
        int n2 = Heap_pop();
        ans += (n1 + n2);
        Heap_push(n1 + n2);
    }
    cout << ans << '\n';
    return 0;
}

#include <iostream>
#include <queue>
 
using namespace std;
 
int arr[100004];
 
int main()
{
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    //priority_queue<int> pq;
 
    // 최소 힙
    priority_queue<int, vector<int>, greater<int>> pq;
 
    int ans = 0;
    int cmp_cnt = 0;
 
    for (int i = 0; i < n; i++)
        pq.push(arr[i]);
 
    // pq.push(-arr[i]) 이렇게도 할 수 있다.
 
    while (!pq.empty())
    {
        if (cmp_cnt == n - 1)
            break;
        int num1 = pq.top();
        pq.pop();
        int num2 = pq.top();
        pq.pop();
 
        ans += (num1 + num2);
        pq.push(num1 + num2);
        cmp_cnt++;
    }
    cout << ans << '\n';
    return 0;
}