[자료구조, 우선순위 큐] BOJ 14698 전생했더니 슬라임 연구자였던 건에 대하여(Hard)

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

14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

 

문제 해결 알고리즘

 

우선순위 큐를 이용해서 맨 위의 두 숫자를 곱한 후 두 수는 pop해주고 곱한 수는 다시 우선순위 큐에 넣는 방식으로 진행한다. 이 때, 결과값에 곱해준다. (모듈러 연산은 결과값 곱해줄 때만 해준다) 마지막에 결과값을 출력해준다.

 

소스 코드

 

#include <bits/stdc++.h>
#define MOD int(1e9+7)
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    int T; cin >> T;
    
    while(T--){
        
        priority_queue<long long, vector<long long>, greater<long long>> pq;
        long long result = 1;
        int N; cin >> N;
        
        for(int i=0;i<N;i++){
            long long n; cin >> n;
            pq.push(n);
        }
        
        while(pq.size() > 1){
            
            long long temp_1 = pq.top();
            pq.pop();
            long long temp_2 = pq.top();
            pq.pop();
            
            long long temp_3 = temp_1 * temp_2;
            
            pq.push(temp_3);
            
            result = (result * (temp_3%MOD)) % MOD;
        }
        
        cout << result << '\n';
        
        
    }
}