[BOJ] 1715 카드 정렬하기

<문제 이해>

숫자 카드 묶음의 개수 N

카드 묶음 각각의 크기가 N번 주어짐

묶음을 합칠 때는 a + b 만큼의 비교가 필요함

즉 a b c 가 있는 묶음에서는 ( a + b ) + ( ( a + b ) + c ) 번의 비교가 필요하다

 

그리디 알고리즘으로 heap 의 top, top + 1을 더한다. 이때 heap은 mean heap으로 구성돼 가장 작은 수가 top에 위치한다.

해당 차례의 최소 값 만을 더하고 다시 heap에 추가해서 반환한다.

처음 제출 시 n = 1일 경우의 예외처리를 진행하지 않아 시간 초과 문제가 발생했다

 if(pq.size() == 1){ 
     cout << 0 << '\n'; 
     return 0; 
}

 를 추가하고 나니 해결됐다. 

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	priority_queue< int, vector<int>, greater<int> > pq;

    int n; cin >> n;
    for(int i=0; i< n; i++){
        int tmp; cin >> tmp;
        pq.push(tmp);
    }
	int sum = 0; 
    if(pq.size() == 1){ 
        cout << 0 << '\n'; 
        return 0; 
    }

	while(!pq.empty()){
		int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        sum += a + b;
        if(pq.empty())break;
		pq.push(a + b);
	}

	cout << sum <<'\n';

	return 0;

}