[C/C++] 백준 #1715 카드 정렬하기(탐욕 알고리즘)

이번 문제는 카드 정렬하기이고요.  이 문제는 정렬된 여러개의 카드 더미가 있을 때, 모두 다 정렬하기 위해서 어떤 순으로 혼합(Merge)를 하는 것이 좋을까입니다.

 

각각 n과 m개의 카드를 가지고 있는 두 더미를 혼합을 하기 위해서는 \(O(n+m)\)의 비교횟수와 이동횟수를 가지고 있다는 것은 잘 알려져 있습니다.  실제 이동 횟수는 \(n+m\)번이 됩니다.

 

Merging

 이 문제에서는 혼합을 하는 과정을 구현하는 것은 아닙니다.  정렬을 하기 위해서는 우리는 두 더미를 혼합하게 되는데, 혼합하는 순서에 따라서 전체적인 이동 횟수가 달라지게 됩니다.  더하기 연산을 할 때, 그 결과값을 모두 더하는 것과 같습니다.

 

3, 5, 7, 9 개의 카드가 있는 더미를 생각한다면,

1) 3 + 5 = 8  --> 총 이동횟수 : 8, 카드 더미 : 7, 8, 9

2) 7 + 8 = 15 --> 총 이동횟수 : 23, 카드 더미 9, 15

3) 9 + 15 = 24 --> 총 이동횟수 : 47, 카드 더미 24

그래서 47이 나오죠.

 

그런데 이것을 다른 순서로 혼합했다면,

1) 7 + 9 = 16 --> 총 이동횟수 : 16, 카드 더미 : 3, 5, 16

2) 5 + 16 = 21 --> 총 이동횟수 : 37, 카드 더미 : 3, 21

3) 3 + 21 = 24 --> 총 이동횟수 : 61, 카드 더미 24

이 경우는 61이 나옵니다.

 

저는 이 문제는 탐욕 알고리즘을 이용해서 구현했습니다.

혼합된 카드에 참여한 카드들은 다음에도 혼합이 될 때, 그 수가 계속 세어진다는 것입니다.  47 = (3+5) + (7+3+5) + (9+3+5+7) 로, 3이란 더미는 3번 사용되었습니다.  5란 수도 3번 사용이 되었고요.  그에 비해 7은 2번, 9는 1번 사용이 되었죠.  61 = (7+9) + (5+7+9) + (3+5+7+9) 가 되어 7과 9가 3번 사용되었고, 5는 2번, 3은 1번 사용되었죠.

 

두개의 카드 더미를 혼합할 때, 어떤 더미를 고를 것인가는, 현재 더미중 가장 작은 카드수를 가지는 2개의 더미를 고르는 것입니다.  그런 후에 그 더미를 다시 넣으면 됩니다.  이를 계산하기 위해서 우선순위 큐나 힙이 필요합니다.  저는 힙을 이용해서 구현했습니다.

 

알고리즘 효율은 힙을 초기화하는데 \(O(n)\), 총 혼합횟수는 n-1번이므로, 혼합 계산하는데 \(O(n \log n)\)이 되어서, \(O(n \log n)\) 알고리즘입니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//    baekjoon #1715 - Sorting Cards
//        - by Aubrey Choi
//        - created at 2019-08-05
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <algorithm>

bool cmp(int a,int b) { return a>b; }
int main()
{
    int n, v[100000], ans=0;
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", v+i);
    std::make_heap(v,v+n,cmp);
    while(n>1)
    {
        int s=0;
        std::pop_heap(v, v+n, cmp); s+=v[--n];
        std::pop_heap(v, v+n, cmp); s+=v[--n];
        ans+=s;
        v[n++]=s; std::push_heap(v, v+n, cmp);
    }
    printf("%d\n", ans);
}