백준 14698 <전생했더니 슬라인 연구자였던 건에 대하여(HARD)>

이 문제의 핵심은 어떻게 큰 수를 적게 곱하는가이다.

 

이렇게 슬라임이 있다면

이렇게 

이렇게 작은 수를 먼저 곱하는 게 적절할 것이다.

 

그러므로 작은수끼리 먼저 곱하는 게 적절하니 우선순위 큐를 사용하면 되는 문제이다.

 

이 문제에서 어려웠던 점은 long값의 계산이었다. 이러한 값이 넘어가는 것을 잘 처리한다면 쉽게 풀리는 문제 유형이다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int divide=1000000007;
	static int t,n,start;
	static PriorityQueue<Long> min;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());
		for(int tc=1;tc<=t;tc++) {
			n=Integer.parseInt(br.readLine());
			start=0;
			min=new PriorityQueue<Long>();
			StringTokenizer st=new StringTokenizer(br.readLine());
			for(int i=0;i<n;i++) {
				long next=Long.parseLong(st.nextToken());
				min.add(next);
			}
			System.out.println(find());
		}

	}
	private static long find() {
		// TODO Auto-generated method stub
		long result=1;
		while(min.size()>=2) {
			long first=min.remove();
			long second=min.remove();
			long next=first*second;
			result=(result*(next%divide))%divide;
			min.add(next);
		}
		return result;
	}
}