백준 1715 G4 카드 정렬하기

생성 2025-03-22 수정 2025-03-24

문제: 카드 정렬하기

잘못된 접근과 올바른 접근

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

처음에는 카드 묶음의 갯수를 오름차순으로 모두 정렬한 후에, 그대로 누적하여 더하는 방법을 취했다.
이게 답이었다면 정답률 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이라고 설정한다.
우선 순위 큐 내에 카드 뭉치가 한개 남을 때 까지 반복한다:
- 두 개를 뽑아서 크기를 더해 뭉친다.
- 두 개를 뭉치면서 크기의 합만큼 비교햇으므로 비교 횟수를 업데이트 해준다.
- 뭉친 카드 크기를 다시 우선 순위 큐에 넣는다.
총 비교 횟수를 출력한다.

코드

#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;
}