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

 

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

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

 

매 단계에서 가장 작은 값 두 개를 곱해야 할 것이라는 직관이 옳다는 것을 확인하면 된다.

 

최초의 슬라임들의 값을

$$ a_1, a_2, a_3, \cdots , a_n$$

이라고 하자. 

 

이들을 어떤 식으로든 결합해서 최종적으로 하나의 슬라임이 되었을 때,

우리가 구해야 하는 값의 형태는

$$ a_1^{e_1} a_2^{e_2} a_3^{e_3} \cdots a_n^{e_n} $$

일 것임은 자명하다.

 

결합 순서에 따라 $e_1, \cdots, e_n$ 은 달라질 것이고 이들의 합이나 곱도 일정치 않지만,

초기 슬라임의 배치는 바꾸고 같은 방식으로 결합한다면 지수는 유지될 것이다.

 

예를 들어 $a_1, a_2$의 위치는 바꾸고 결합 순서는 같게 한다면

$$ a_2^{e_1} a_1^{e_2} a_3^{e_3} \cdots a_n^{e_n} $$

를 얻게 된다.

 

1. 이 시점에서 $a_i$ 들이 오름 차순으로 정렬된 순서였다면 $e_i$ 들은 내림 차순이어야 함을 알게 된다.

2. 그리고 결정적인 관찰은 최초에 결합된 두 수는 같은 지수를 가져야 한다는 것이다.

 

2 번이 결정적인 이유는 가장 작은 수와 짝지어지는 것은 최다 횟수로 사용된다는 뜻이기 때문이다.

따라서 각 단계에서 가장 작은 수와 짝지어져야 하는 것은 그 다음으로 작은 수임을 알 수 있다.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll mmod=1e9+7;

void solve(){
    int n; scanf("%d",&n);
    
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    for(int i=0;i<n;i++) {
        ll t; scanf("%lld",&t);
        pq.push(t);
    }
    
    ll ans=1;
    while(pq.size()>1){
        ll a=pq.top(); pq.pop();
        ll b=pq.top(); pq.pop();
        a=a*b;
        ans=(a%mmod)*ans%mmod;
        pq.push(a);
    }
    printf("%lld\n",ans%mmod);
}

int main(){
    int T; scanf("%d",&T);
    while(T--)
        solve();
}

 

문제의 조건에서 슬라임들의 에너지의 곱은 long long 을 벗어나지 않을 것임이 보장되어 있다.

즉, ans 와 달리 mod 연산을 적용할 필요가 없다.