백준 문제 1715번 카드 정렬하기 문제풀이 c++

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

1715번: 카드 정렬하기

 

문제해석

 

문제를 읽고 조금 생각해보니 최소 비교를 구하려면 계속 최소의 비교를 하면 되면 되지 않을까 하는 결론에 도달했다.

 

1.카드 묶음중 가장 작은 두개의 뭉치를 골라 비교를한다.

2.비교를 하면 두 뭉치는 합쳐서 하나의 뭉치가 된다.

 

1번과 2번의 과정을 카드 뭉치가 1개가 될 때까지 반복하자.

 

이 과정을 따라 10 20 40이 입력이 주어졌을때를 보자

 

가장 작은 뭉치 두개는 10 20이다 둘이 합쳐서 30짜리 카드 뭉치가 된다.

카드 뭉치는 30 40이된다. 

가장 작은 뭉치 두개는 30 40이다 둘이 합쳐서 70짜리 카드 뭉치가 된다.

 

총 비교횟수 (10+20)+(30+40)=100이 됨을 확인 할 수있다.

 

가장 작은 두개 뭉치를 골라야하는데 정렬을 하여 할 수도 있지만 이러면 1 2 후 정렬을 게속 해야하는데 이러면 아마 시간 초과가 날 것이다.

 

우선순위 큐를 사용하면 매번 정렬하지않고 가장 작은 값을  얻을 수 있다.

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
typedef long long int ll;
using namespace std;
priority_queue < ll, vector<ll>, greater<ll> > pq;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n,input,sum; cin>>n;
    for(ll i=0; i<n; i++)
    {
        cin>>input;
        pq.push(input);
    }
    ll ans=0;
    while(pq.size()>1)
    {
        sum=0;
        ll x=pq.top();
        pq.pop();
        ll y=pq.top();
        pq.pop();
        sum=sum+x+y;
        ans=ans+sum;
        pq.push(sum);
    }
    cout<<ans;
}