koitp SDS_TEST_CALCULATOR 오래된계산기

문제 링크입니다: https://koitp.org/problem/SDS_TEST_CALCULATOR/read/

힙을 이용해야지만 시간 내에 AC를 받을 수 있는 정렬 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. 최소 힙을 구성하는 우선순위 큐를 선언해주고 숫자들을 우선순위 큐에 넣어줍니다.

2. 최소 힙에서 두 개의 숫자 즉, 최소 숫자와 두 번째로 작은 숫자를 꺼내서 더해줍니다.

3. 2번의 연산 결과를 합에 더해주고, 2번의 연산 결과를 우선순위 큐에 넣어줍니다.

4. 2~3번을 우선순위 큐 크기가 1이 될 때까지 반복해줍니다.

#include <iostream>

#include <vector>

#include <queue>

#include <functional>

#include <algorithm>

using namespace std;

 

int N;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int test_case;

        cin >> test_case;

 

        for (int i = 1; i <= test_case; i++)

        {

                 int N;

                 cin >> N;

 

                 //minHeap(최소 힙)

                 priority_queue<long long, vector<long long>, greater<long long>> pq;

 

                 for (int j = 0; j < N; j++)

                 {

                         int num;

                         cin >> num;

 

                         pq.push(num);

                 }

 

                 long long sum = 0;

                 while (1)

                 {

                         long long temp = 0;

                         //최소힙에서 두개의 숫자를 꺼내고 더해준다

                         for (int j = 0; j < 2; j++)

                         {

                                 temp += pq.top();

                                 pq.pop();

                         }

 

                         //위 연산 결과를 합에 더해준다

                         sum += temp;

                        

                         //위 연산 결과를 우선순위 큐에 다시 넣어준다

                         pq.push(temp);

                         if (pq.size() == 1)

                                 break;

                 }

                 cout << "#" << i << " " << sum << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~