C++ / 1715 / 카드 정렬하기 ( 그리디 알고리즘 )

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

문제 요약

n개의 카드 묶음이 있습니다.

두 묶음 씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가  매우 달라집니다.

예를 들어 10장 20장 40장의 묶음이 있다면 ( 10 + 20 ) + ( 30 + 40 ) = 100번의 비교가 필요합니다.

그러나 10장과 40장을 먼저 합치고 20장을 합친다면 ( 10 + 40 ) + ( 50 + 20 ) = 120번의 비교가 필요하므로 덜 효율적인 방법입니다.

최소한 몇 번의 비교가 필요한지 구해야 합니다. 

문제 풀이

1. priority_queue로 큐를 만듭니다. priority_queue는 시간 복잡도도 낮고 항상 정렬한 상태이기 때문에 유용합니다.

2. 카드 묶음을 입력 받습니다.

3. 최소 2개 이상일 때까지 계속 묶음을 합치도록 반복문 조건을 줍니다.

4. top()으로 큐의 가장 위에 값을 가져옵니다. 그후 pop()으로 사용한 값을 없애줍니다. 이걸 2번 하면 가장 작은 2값을 가져 온 후 삭제 할 수 있습니다.

5. 그 두 값을 더하고 합계 변수인 sum에 더합니다.

6. sum을 큐에 푸시합니다. 

 

주의 할점

처음엔 가장 작은 값 2개지만 그 후로는 더한 값 + 다음 값을 계속 반복해야 합니다.

다음 값이 sum보다 작은  경우 ex ) sum = 30  다음 값 = 25  다다음 값 = 26 이런식으로 값이 있다고 했을때

( sum + 다음 값 ) +( 55 + 다다음 값 ) =  136 이기 때문에 정렬한 (다음 값 + 다다음 값) + (51 + 30) = 132보다 더 비효율적이게 합치게 됩니다.

그래서 sum을 큐에 넣은 후 매번 재 정렬할 필요가 생겨 priority_queue를 사용해야 용이하게 됩니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
//프리오리티 큐는 항상 정렬함, 정렬 비용이 쌈
priority_queue<long long, vector<long long>, greater<long long>> pq;

long long int a, n, sum = 0;
vector<int> p;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        pq.push(a);
    }
    // 최소 두 개 이상일 때까지 계속 합침
    while (pq.size() > 1)
    {
        // 가장 작은 두 값을 꺼내서 더함
        long long t1 = pq.top(); 
        pq.pop();
        long long t2 = pq.top(); 
        pq.pop();
        long long combined = t1 + t2;

      	// 계산한 값을 sum에 더함
        sum += combined;  
        // 합친 값을 다시 큐에 넣음
        pq.push(combined);
    }
    cout << sum;
    return 0;
}

반응형

예제

100

결과