Beakjoon 1715 카드 정렬하기

20 Jan 2021 in Algorithm

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

나의 풀이

이 문제는 현재 상황에서 항상 가장 작은 것 2개를 합해야 값이 가장 작기 때문에 priority queue를 사용하여 해결할 수 있다.
이 때 c++에서 제공하는 priority queue는 기본적으로 오름차순이기 때문에 push, pop할 때 음수로 바꿔 처리하였다.

풀이 코드 : 1715 카드 정렬하기

#include <stdio.h>
#include <queue>

using namespace std;

int main(){
    int N, num;
    scanf("%d",&N);
    priority_queue<int> heap;
    for(int i=0;i<N;i++){
        scanf("%d", &num);
        heap.push(-num);
    }

    int num1, num2, sum, answer = 0;

    while(heap.size() >= 2){
        sum = 0;
        num1 = -heap.top();
        heap.pop();
        num2 = -heap.top();
        heap.pop();
        sum = num1 + num2;
        answer += sum;
        heap.push(-sum);
    }

    printf("%d",answer);
}

채점결과