백준 1715 G4 카드 정렬하기

Date/Lastmod

03-22/25 03-24/25

Section

PS

Title

백준 1715 G4 카드 정렬하기

Ps-Tags

그리디우선순위 큐

Solved

03-24/2505-28/25

#¹ 잘못된 접근과 올바른 접근

#² [잘못된 접근]: 오름차 순으로 정렬하고 다 더하기

처음에는 카드 묶음의 갯수를 오름차순으로 모두 정렬한 후에, 그대로 누적하여 더하는 방법을 취했다.
이게 답이었다면 정답률 30%대 문제일리가 없다고 생각하긴 했는데, 역시나 틀렸다.

그런데 왜 틀린걸까? 반례는 다음과 같다:

예를 들어 카드 묶음이 {5, 10, 12, 13} 4개가 있고, 이미 오름차 순으로 정렬되어 있다.

나의 처음 방식을 적용하여, 이 순서대로 계속 누적해 더해 보자. 그러면
(5 + 10) + (15 + 12) + (27 + 13) = 82 이다.

하지만, 실제로는
(5 + 10) + (12 + 13) + (15 + 25) = 80 이 맞다.

왜 이런 차이가 발생할까?

#² [올바른 접근]: 더할 때마다 새 카드 묶음이 계속 생긴다

두 카드 묶음을 더하면, 새로운 크기의 카드 묶음이 생긴다.

둘을 더해 새로 생성된 새로운 크기의 카드 묶음이, 기존 카드 묶음 중에서 최소라는 보장이 없다.
새 카드 묶음을 만들면, 기존 카드 묶음 배열의 정렬이 깨지기 때문 이다.

배열 같은 것을 사용하면 정렬에 소요되는 $O(N\log{N})$을 매 $N$ 요소에 대해서 수행해야 하므로 총 복잡도는 $O(N^2\log{N})$이다.

하지만, 우린 이미 뽑고 넣을 때마다 최소 혹은 최대값에 빠르게 접근할 수 있는 자료구조 우선순위 큐 를 알고 있으며, 우선 순위 큐는 $N$ 개 요소에 대해 삽입($O(\log{N})$)과 삭제($O(\log{N})$)를 반복하므로 총 복잡도는 $O(N\log{N})$이다.

#¹ 알고리즘

• 입력 받은 카드 뭉치들을 모조리 우선 순위 큐에 넣는다.
• 총 비교 횟수를 0이라고 설정한다.
• 우선 순위 큐 내에 카드 뭉치가 한개 남을 때 까지 반복한다:
  • 두 개를 뽑아서 크기를 더해 뭉친다.
  • 두 개를 뭉치면서 크기의 합만큼 비교햇으므로 비교 횟수를 업데이트 해준다.
  • 뭉친 카드 크기를 다시 우선 순위 큐에 넣는다.
• 총 비교 횟수를 출력한다.

#¹ 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

using namespace std;

int N; 
vector<int> card_packs;
priority_queue<int, vector<int>, greater<int>> pq; 

int main() {
  cin >> N;
  for (int i = 0; i < N; ++i) {
    int card_pack; cin >> card_pack;
    pq.push(card_pack);
  }

  int comparison_count = 0;

  while (pq.size() > 1) {

    int l = pq.top(); 
    pq.pop();

    int r = pq.top();
    pq.pop();

    int sum = l + r;

    comparison_count += sum;
    pq.push(sum);
  }

  cout << comparison_count;
}