[BOJ_1715_RN] 카드 정렬하기 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/1715

문제 해결에 필요한 알고리즘 : 그리디 알고리즘

해설

가장 작은 두 수끼리 계속 합쳐주는 것이 가장 최적이다. priority queue를 이용하여 문제를 해결 할 수 있다. 모든 수를 큐에 삽입한 후 가장 작은 두 수를 꺼내 연산한 뒤 결과를 다시 큐에 넣어주면 된다. 이렇게 큐에 한가지의 숫자가 남을 때 까지 하면 최소로 비교하는 횟수를 알 수 있다.

정당성 증명

S(A, b)를 A라는 수의 집합과 b라는 수를 포함하는 카드의 집합이라고 정의한다.

MIN(S) 는 수의 집합에서 가장 최적으로 비교하는 횟수라고 정의한다.

S(A, b), S(A, c)가 있을 때 b > c 라고 하면,

MIN(S(A, b)) > MIN(S(A, c)) 가 됨을 쉽게 알 수 있다.

가장 작은 두 수를 합치지 않았을 때는 무조건 손해를 보는 상황이 생긴다.

따라서 가장 작은 두 수를 합치는 것이 가장 최적임을 알 수 있다.

시간복잡도

큐에 값을 넣는데는  만큼 걸린다. 이 때 처음 삽입할 때  만큼 걸리게 된다. 또 큐에 있는 값을 pop하고 push하는데  만큼 걸린다. 또 N번 진행하므로  만큼 걸리게 된다.

따라서 시간복잡도는  이다.

카드 정렬하기 코드 [ C++ ]

#include <cstdio>
#include <vector>
#include <queue>
struct cmp {
    bool operator() (int i, int j) {
        return i > j;
    }
};
int main() {
    int n, res = 0;
    std::priority_queue < int, std::vector < int >, cmp > pq;
    scanf("%d", &n);
    for (int i = n; i--; ) {
        int m;
        scanf("%d", &m);
        pq.push(m);
    }
    for (; pq.size() > 1; ) {
        int t1 = pq.top(); pq.pop();
        int t2 = pq.top(); pq.pop();
        res += t1 + t2;
        pq.push(t1 + t2);
    }
    printf("%d", res);
    return 0;
}