84. C++ 백준 1715 번 카드 정렬하기 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘인 BOJ 1715 번 카드 정렬하기 입니다.

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

1715번: 카드 정렬하기

 

 

먼저  백준 1715 번 C++ 정답 코드입니다.

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> heap;

int main(){
    int N, input, A, B, res = 0;
    cin >> N;

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

    for (int i = 1; i < N; i++){
        A = heap.top(); heap.pop();
        B = heap.top(); heap.pop();
        res += A + B;
        heap.push(A + B);
    }
    cout << res;

    return 0;
}

두 카드 묶음 A, B를 합쳐 정렬된 하나의 카드 묶음으로 만들기 위해서는 A + B 번의 비교가 필요합니다.

A, B가 작으면 작을 수록 비교하는 횟수가 적어지기 때문에 가능한 작은 크기의 카드 묶음으로 만들어야 되고,

이를 위해서는 가장 작은 카드의 묶음 2개를 선택하여 새로운 카드 묶음으로 만들며 비교해나가면 됩니다.

만약 큰 카드의 묶음을 뽑아서 새로운 카드 묶음으로 만들어가면 바교해야되는 카드 수가 점점 늘어나겠죠.

 

즉 카드 묶음의 집합에서 가장 작은 크기의 두 카드 묶음 A, B를 뽑아서 비교횟수를 더하고,

새로 만들어진 A +B 크기의 카드 묶음을 집합에 넣으며

비교할 카드 묶음이 없어질 때 까지 반복하면 됩니다.

 

위의 직관으로 C++ 코드를 구현해봅시다.

최소값, 최대값을 구하는데 가장 효율적인 자료구조인 heap을 구현해줍니다.

#include <queue>

priority_queue<int, vector<int>, greater<int>> heap;

 

카드 묶음을 묶음 개수만큼 입력받아 힙에 넣어줍니다.

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

 

이후 N-1 번 동안 (카드 묶음이 1개 남을때 까지)

가장 작은 크기의 두 카드 묶음을 하나의 카드 묶음으로 만들고, 계산 횟수를 더합니다.

그리고 만들어진 새로운 카드 묶음을 힙에 다시 넣어줍니다.

for (int i = 1; i < N; i++){
    A = heap.top(); heap.pop();
    B = heap.top(); heap.pop();
    res += A + B;
    heap.push(A + B);
}

 

카드묶음이 하나 남으면 지금까지 연산한 횟수를 출력하면 됩니다.

cout << res;

 

백준 1715 번 카드 정렬하기 C++ 최종 코드 입니다.

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> heap;

int main(){
    int N, input, A, B, res = 0;
    cin >> N;

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

    for (int i = 1; i < N; i++){
        A = heap.top(); heap.pop();
        B = heap.top(); heap.pop();
        res += A + B;
        heap.push(A + B);
    }
    cout << res;

    return 0;
}

 

사실 문제 자체는 어렵지 않지만 시간 내에 빠른 속도로 처리하기 위해서는 

heap이라는 자료구조에 대해 알고있어야 됩니다.

 

백준 1715 번 카드 정렬하기 C++ 코드와 함께 자세한 설명 이었습니다.

감사합니다.