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

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

수들의 범위가 그동안 문제들에서 보지 못했던 범위여서..

범위로 고생 좀 하겠구나 하고 살짝 겁이 났다.

우선 전기 에너지를 가장 작게 만드는게 포인트인 것 같다.

전기 에너지를 작게 만든다 ?! -> 작은 에너지를 가진 슬라임부터 합성해보자!

작은 에너지를 가진 슬라임들로 짝을 만들려면 우선순위 큐를 사용해야 한다.

3 10 2 8 14

위 슬라임들을 우선순위 큐에 넣어보면 아래와 같다.

2 3 8 10 14 

작은 에너지를 가진 슬라임들부터 합성해보면 동작은 아래와 같다.

2 3 8 10 14

6 8 10 14

6 8 10 14

10 14 48

10 14 48

48 140

48 140

6720

합성에 사용된 에너지를 모두 곱하면

6 * 48 * 140 * 6720 = 270,950,400

#. Code

우선, 2 × 1018  범위를 담으려면 long 자료형을 사용해야 한다.

그리고 조심해야 하는 부분은

합성하고 난 후에 생기는 슬라임의 에너지의 양이 2 × 1018 이하라고 했지만,

지금까지 비용에 누적해서 곱하는 과정에서 cost의 범위가 long 범위를 넘어갈 수 있다.

아래와 같이

cost = (cost * (mul % MOD)) % MOD; 

합성하고 난 후에 생기는 슬라임의 에너지양을 MOD 해준 결과에 비용을 누적곱해준 후 MOD를 다시 해주어야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ14698 {
 
    static final int MOD = 1_000_000_007;
    static int N;
    static PriorityQueue<Long> pq;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        StringTokenizer st;
        
        pq = new PriorityQueue<>();
        
        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            
            N = Integer.parseInt(br.readLine());
            
            pq.clear();
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                pq.add(Long.parseLong((st.nextToken())));
            }
            
            sb.append(process() + "\n");
        }
        
        System.out.println(sb);
    }
 
    private static long process() {
 
        long cost = 1, mul = 0;
        // N 마리의 슬라임을 모두 합성해서 1마리의 슬라임으로.
        while(pq.size() > 1) {
            // 각 합성 단계마다 필요한 전기 에너지들을 모두 곱한 값이 비용
            mul = pq.poll() * pq.poll();
            cost = (cost * (mul % MOD)) % MOD;
 
            pq.add(mul);
        }
        
        return cost;
    }
    
}