백준 1715: 카드 정렬하기

📃 문제: 백준 1715(카드 정렬하기)

1715번: 카드 정렬하기

[문제]

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

 

 

 

🥇 난이도: 골드 4

 

 

😲 사용한 개념: 그리디 알고리즘

 

💡 그리디 알고리즘이란?

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 결과에서의 최선의 선택지라고 가정하는 알고리즘이다.

최적해를 구하는 근사적인 방법으로 당장 눈 앞에 있는 최적의 해를 선택해가는 방식으로 진행되기 때문에 탐욕적인(=Greedy) 알고리즘이라고 불린다.

 

수행과정은 아래와 같다.

1) 현재 상태에서의 최선의 해를 선택
2) 해가 전체 문제 제약 조건에 벗어나지 않는지 검사
3) 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 아니라면 1로 돌아가 동일 작업을 반복.

 

 

 

📖 풀이 사고 과정

 

⚠️여기서 잠깐! ⚠️

💬C++ STL, priority_queue에 대하여...

 

prioirty_queue는 default값으로, 내림차순 정렬로 가장 큰 값이 queue의 top에 위치하도록 설정되어있다.

문제에서 필요한 우선순위로 정렬되는 우선순위 큐를 만들기 위해서는 우선순위를 비교하는데 사용하는 Comparator(비교함수)를 명시해주어야 한다!

 

priority_queue의 템플릿 선언은 일반적으로 세가지 주요 구성 요소로 이루어져있다.

바로 1️⃣요소 타입 2️⃣컨테이너 타입, 3️⃣비교 함수이다.

 

priority_queue<int> pq; 선언시 생성되는 default 구성 요소는 priority_queue<int, vector<int>, less<int>> pq;

와 같은 설정을 가지고 있다.

 

이와 반대로 내림차순의 priority_queue를 생성하기 위해선, priority_queue<int, vector<int>, greater<int>>pq;를 선언해주면 된다.

 

greater<int> 함수는 두 정수를 비교하고, 첫번째 인자가 두번째 인자보다 크면 true를 반환한다. priority_queue는 true를 우선순위가 낮다는 신호로 해석하여, 실제로는 더 큰 값들이 우선순위가 낮게 설정된다.

 

 

 

 

👩‍💻 구현 코드(c++ 사용)

#include <iostream>
#include <queue>
using namespace std;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, num, sum, total_sum=0;
    priority_queue<int, vector<int>, greater<int>> pq;

    cin >> N;

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

    while (pq.size() > 1) {
        //가장 작은 두 카드뭉치 합칠 시의 비교횟수 구하기 + 두 카드뭉치 pop하기
        sum = 0;
        sum += pq.top();
        pq.pop();
        sum += pq.top();
        pq.pop();

        total_sum += sum;
        //합쳐진 카드뭉치 값 추가
        pq.push(sum);
    }
    cout << total_sum << endl;

    return 0;
}