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

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

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

우선순위 큐를 활용한 그리디 문제

 

언뜻 보면 파일 합치기(11066번)과 비슷해 보일 수 있지만 이 문제의 경우에는 연속해있는 파일만 합칠 수 있다던지 하는 조건이 없으므로 현재 상황에서 가장 에너지가 작은 슬라임 두 개를 합치면 된다.

 

매번 가장 에너지가 작은 슬라임 두 개를 찾기 위해서 우선 순위 큐를 사용할 것이고 가중치가 가장 적은 것을 선택해야 되므로 마이너스로 우선 순위 큐에 푸쉬해줄 것이다.

 

AC code

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		ll N,t,sol=1;
		priority_queue<ll> pq;
		cin>>N;
		for(int i=0;i<N;i++) {
			cin>>t;
			pq.push(-t);
		}
		while(1) {
			t=pq.top();
			pq.pop();
			if(pq.empty()) break;
			t=t*pq.top();
			pq.pop();
			sol=sol*(t%MOD)%MOD;
			pq.push(-t);
		}
		cout<<sol<<"\n";
	}
}

주의해야 될 점은 MOD연산을 하는 부분이다.

우선 순위 큐에 넣을 때는 모드 연산을 하면 안 되고 답을 구하는 것에서만 모드 연산을 해야되며 전체 곱은 물론, 곱해주기 전에도 모드 연산을 한 값을 곱해줘야 된다.