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

[적용한 알고리즘]

그리디, 우선순위 큐

 

[아이디어]

제일 작은 거 2개만 필요하니까 우선 순위 큐를 이용하자

 

[생각의 흐름 / 절차] 

1. n개의 입력을 우선순위 큐(pq)에 담는다.

2. 매번 2개씩 뽑아 그 두 개를 더한 값은 다시 pq에 넣는다.

3. pq의 사이즈가 1이라면 그때 멈추고 출력한다.

 

[교훈]

사이즈가 1인걸 판별하는 if문의 위치를 잘못잡아 계속 틀린 답이 나왔다.

애초에 사이즈가 1인 경우를 고려 안했기 때문이다.

그래서 범위의 경계값에 좀 더 주의하도록 하자.

 

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

int main(){
    int n;
    priority_queue<int, vector<int>, greater<int>> pq;
    scanf("%d", &n);

    for (int i = 0; i < n; i++){
        int x; scanf("%d", &x);
        pq.push(x);
    }

    int ans = 0;

    while (true){
        if (pq.size() == 1){
            printf("%d\n", ans);
            return 0;
        }
        
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        pq.push(a + b);
        ans += (a + b);
    }
}