[BOJ] 1715_카드 정렬하기

카드 정렬하기

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

1715번: 카드 정렬하기

 

10 20 40의 카드 묶음들이 있을 때 최소 비교를 하기 위해서는 값이 오름차순으로 정렬되어 있어야 한다.

위 처럼 오름차순으로 정렬되어 있을 때 10 + 20 = 30이 또 다른 묶음이 되어 10과 20의 묶음을 제외한 나머지 카드 더미들과 비교를 수행해야한다.
10과 20은 이미 30번 수행을 했고, 이제 이 30개의 더미와 40개의 더미를 비교하면 70번의 비교가 필요하다.
따라서, 30 + 70 = 100번이 최소 비교가 된다.

60을 추가해서 생각해보자.
(10+20) + (30+40) + (70+60) = 230
30 + 70 + 130 = 230번의 비교가 필요할 것이다.

두개의 더미 합은 새로운 더미이므로 이를 리스트에 넣을때마다 정렬되어야 한다.
즉, 배열에 삽입하고 sort를 수행해야 하지만, Heap이나 priority queue를 이용하여 삽입할 때 정렬되게끔 한다면, 더 효율적으로 수행이 가능할 것이다.

priority queue를 이용하여 코드를 짜면 다음과 같다.

 

• 정답 코드

    #include<iostream>
    #include<functional>
    #include<queue>
    using namespace std;
    #define maxNum 100001
    int list[maxNum];
    int n;
    priority_queue<int, vector<int>, greater<int>> list_;
  
    int main() {
        cin >> n;
  
        for (int i = 0; i < n; i++){
            int t;
            cin >> t;
            list_.push(t);
        }
  
        int sum = 0, totalsum = 0;
  
        while (list_.size() != 1) {
            sum += list_.top();
            list_.pop();
  
            sum += list_.top();
            list_.pop();
  
            list_.push(sum);
            totalsum += sum;
            sum = 0;
        }
  
        cout << totalsum;
  
        return 0;
    }