[백준 - 14698] 골드4 - 전생했더니 슬라임 연구자였던 건에 대하여(Hard)

www.acmicpc.net/problem/14698

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

1. 유형

그리디, 우선순위큐

 

2. 풀이

문제에서 요구하는 값이 가장 작으려면

 

매 상황마다 가장 작은 슬라임 2개를 합성하면 가장 작은 결과를 얻는게 가능하다.

 

이때 사용하는 자료구조가 우선순위큐이다.

 

문제에서 가장 어려운 부분은 숫자의 범위 초과이다.

 

아래처럼 mod연산을 통해서 long타입을 넘길거 같으면 나머지 연산을 해야한다.

java를 쓰면 시간초과가 날 수 있다.

 

테스터 케이스를 전부다 돌기 때문이다. 이때 StringBuilder를 사용해서 마지막에 한번만 

 

출력할 수 있도록 한다.

 

3. 코드

package 구현;

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

public class Beak_전생했더니슬라임연구자였던건에대하여 {
	static int mod = 1000000007;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int T = Integer.valueOf(st.nextToken());
		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(in.readLine(), " ");
			int N = Integer.valueOf(st.nextToken());
			PriorityQueue<Long> pq = new PriorityQueue<>();
			st = new StringTokenizer(in.readLine(), " ");
			for (int i = 0; i < N; i++) {
				pq.add(Long.valueOf(st.nextToken()));
			}
			long res = 1;
			while (!pq.isEmpty()) {
				if (pq.size() == 1) {
					break;
				}
				long val1 = pq.poll();
				long val2 = pq.poll();
				res = (res * ((val1 * val2)%mod)) % mod;
				pq.add((val1 * val2));
			}
			sb.append(String.valueOf(res) + '\n');

		}
		System.out.println(sb);
	}
}