백준 1715 카드 정렬하기

문제링크 : https://www.acmicpc.net/problem/1715

 

아이디어

• 두묶음씩 합칠때, 카드 개수가 많은 묶음일수록 합쳐지는 횟수가 적어야함
• 정렬한다음, 두개씩 묶어나감
  • 이렇게하면 문제 발생
  • A,B,C,D 에서, A,B 더한값이 C,D보다 작을경우엔
  • (A + B) + (C+D) 보다, ((A+B)+C)+D 가 맞음
• 그럼 정렬해서 앞의 두개씩만 더하자
  • pq 사용

 

시간복잡도 계산

• 처음 정렬 : O(NlgN)
• 앞의 두개씩 계산 : O(N * lgN)
• 합 : O(NlgN)

 

인트 계산

• 최대 카드 합의 값 : 1e3* 1e5 * lg(1e5) = 1e8 + 20 > 2e9, 안전하게 ll 사용

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
 
using namespace std;
typedef long long ll;
 
 
int main() {
    int N; cin >> N;
    priority_queue<ll,vector<ll>, greater<ll>> pq;
 
    for(int i=0; i<N; i++) {
        ll a; cin >> a;
        pq.push(a);
    }
    
    
    ll rs=0;
    
    while(pq.size() != 1) {
        ll a = pq.top(); pq.pop();
        ll b = pq.top(); pq.pop();
        pq.push(a+b);
        rs+=(a+b);
    }
    
    
    cout << rs << '\n';
    
    return 0;
}
 

 

문제유형

• 그리디 - 두개씩 합치기
  • 더할수록 이전 비용까지 합해서 발생하는 경우
  • 큰 수는 가장 마지막에 계산
  • 우선순위 큐를 사용하여 가장 앞에 두개씩 더해서 추가