[백준OJ] 1715번 카드 정렬하기

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

---

 

풀이)

문제를 읽어보니

1) 제일 작은 수+두번째로 작은수

2) 1번에서 구한 수 + 그다음 작은 수

3) 2번에서 구한 수 + 그다음 작은 수

4) 3번에서 구한 수 + 그다음 작은 수

.....

가 된다.

 

따라서 우선순위 큐에 모든 수를 넣은뒤에, 작은수부터 2개씩 꺼낸뒤, 더해준 결과를 sum에 저장시키고, 더해준 결과를 다시 우선순위 큐에 넣어준다.

이때 우선순위 큐의 사이즈가 1이 될때까지 해주면 된다.

 

시간복잡도)

우선순위 큐의 push가 O(logN), pop이 O(logN)이 걸린다.

입력에서 푸쉬를 N번하므로 O(NlogN)

연산에서 push를 N-1번 하므로 O(NlogN), pop을 2*(N-1)번 하므로 O(NlogN)이 걸린다.

따라서 총 시간복잡도는 O(NlogN) 이 된다.

 

코드)

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

priority_queue<int> card;
int main(){
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++){
        int data;
        cin>>data;
        card.push(-data);
    }
    
    int sum=0;
        while(card.size()!=1){
            int first=-card.top();
            card.pop();
            int second=-card.top();
            card.pop();
            int add=first+second;
            sum+=add;
            card.push(-add);
        }
    cout<<sum<<"\n";
}