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

백준의 카드 정렬하기(1715) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

카드를 정렬하는데 비교해야 하는 최소의 횟수를 구해야 하는 문제이다.

먼저 간단하게 생각해보면, 카드의 장수가 적은 카드 묶음 끼리 더하는 것이 그 횟수를 줄일 수 있다 라는 것을 알 수 있다.

입력예제만 보더라도, [ 10 , 20 , 40 ] 이 있을 때, [ 10 , 40 ] 을 합친 후, [ 50 , 20 ] 을 하는 것 보다는

[ 10 , 20 ] 을 먼저 합친 후, [ 30 , 40 ] 을 합치는 것이 비교의 횟수를 줄일 수 있다는 것을 확인할 수 있다.

또한, 카드 묶음을 합치는 횟수는 N - 1번이 된다.

[ 10 , 20 , 40 ] 이렇게 총 3개의 카드 묶음이 존재할 때, 카드를 합치는 횟수만 본다면

[ 10 , 20 ] 1번

[ 30 , 40 ] 2번 이 된다.

또 다른 예로 [ 10 , 20 , 30 , 40 ] 이 있다고 생각해보면

[ 10 , 20 ] - 1번

[ 30 , 30 ] - 2번

[ 60 , 40 ] - 3번

총 N - 1번 합치게 되면 모든 카드를 비교하는 것이 된다.

즉, 우리는 "현재 존재하는 카드 묶음 중에서, 가장 적은 2개의 묶음을 우선적으로 계산" 하는 것이 정답이라는 것을

눈치챌 수 있다.

따라서, 이 부분을 힙으로 구현해 보았다. 우선순위큐를 이용해서 카드의 장수가 적은 카드묶음 일수록 우선순위를

갖게 만들어서, 큐의 가장 top()에 있는 2개의 묶음을 합치는 과정을 "N - 1번" 동안 반복해 주었다.

아직 힙에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 자료구조 힙(Heap) 알아보기(Click) ]

소스코드는 본인이 힙을 직접 구현한 버젼과, STL Priority Queue를 사용한 2가지 방식 모두 첨부해 놓겠다.

[ 소스코드 (Priority Queue Ver) ]

#include<iostream>
#include<queue>
 
#define MAX 100000
#define endl "\n"
using namespace std;
 
int N;
int Arr[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    priority_queue<int> PQ;
    for (int i = 0; i < N; i++) PQ.push(-Arr[i]);
    
    int Answer = 0;
    int Compare_Cnt = 0;
 
    while (PQ.empty() == 0)
    {
        if (Compare_Cnt == N - 1) break;
        int Num1 = -PQ.top(); PQ.pop();
        int Num2 = -PQ.top(); PQ.pop();
        
        Answer = Answer + (Num1 + Num2);
        PQ.push(-(Num1 + Num2));
        Compare_Cnt++;
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ 소스코드 Heap구현 Ver ]

#include<iostream>
#include<queue>
 
#define MAX 100000
#define endl "\n"
using namespace std;
 
int N, Heap_Idx;
int Arr[MAX];
int Heap_Array[MAX + 10];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Heap_push(int Data)
{
    int Idx = ++Heap_Idx;
    Heap_Array[Idx] = Data;
    while ((Idx != 1) && (Data < Heap_Array[Idx / 2]))
    {
        swap(Heap_Array[Idx], Heap_Array[Idx / 2]);
        Idx = Idx / 2;
    }
}
 
int Heap_pop()
{
    int Result = Heap_Array[1];
    Heap_Array[1] = Heap_Array[Heap_Idx--];
 
    int Parent = 1;
    int Child;
    while (1)
    {
        Child = Parent * 2;
        if (Child + 1 <= Heap_Idx && Heap_Array[Child + 1] < Heap_Array[Child]) Child++;
        if (Child > Heap_Idx || Heap_Array[Parent] < Heap_Array[Child]) break;
        swap(Heap_Array[Child], Heap_Array[Parent]);
        Parent = Child;
    }
    return Result;
}
 
void Solution()
{
    int Answer = 0;
    int Compare_Cnt = N - 1;
    for (int i = 0; i < N; i++) Heap_push(Arr[i]);
    for (int i = 0; i < Compare_Cnt; i++)
    {
        int N1 = Heap_pop();
        int N2 = Heap_pop();
        Answer = Answer + (N1 + N2);
        Heap_push(N1 + N2);
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}