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

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

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

슬라임 커엽다

---

※  문제를 요약하면 아래와 같습니다.

▶ 청년이 죽어서 슬라임 연구자로 환생, 원래 인생을 되찾기 위해 슬라임 연구 ( 아마 메이플 월드,,? )

▶ 슬라임은 모두 개인 에너지 값을 정수로 가지고 있으며 슬라임을 적절히 합성하여 1마리로 만드는 것이 목표

▶ 슬라임은 2마리에서 1마리로 합성만 가능하며 이 때 각 슬라임의 정수를 곱한 값 만큼 에너지가 소요

▶ 필요한 에너지를 최소로 하여 슬라임을 합성을 하는 것이 목표

▶ Input : 첫번째 줄에 테스트 케이스의 수 T, 이후 각 테스트 케이스의 첫 번째 줄에 슬라임의 수 N이 주어지고,

                 이후 두 번째 줄에는 공백을 구분으로 N개의 각 슬라임의 에너지가 입력

                 끝까지 합성하고 난 후에 생기는 슬라임의 에너지의 양이 2 x 10^18 이하라는 것을 보장

▶ Output : 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의

                    최소값을 1,000,000,007로 나눈 나머지 출력, 에너지가 필요없을 경우 1 출력

---

◈ Input - 1

2
5
3 10 2 8 14
1
13

◈ Output - 1

270950400
1

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 각 슬라임을 오름차순으로 정렬하면서 가장 앞의 두 슬라임을 곱하면 최소 비용으로 합성

▶ 합성 결과를 자료구조에 다시 저장

▶ 위의 필요한 과정을 한 번에 구현 할 수 있는 우선순위 큐 자료 구조를 활용 (최소큐)

     1. 입력값을 전부 PriorityQueue에 담고, ( 디폴트로 오름차순으로 정렬되어 최소큐 형태 유지)

     2. 최소큐 값을 2번 뽑아 2개의 값을 곱하고, 그 값을 다시 ProrityQueue에 추가

     3. 또한 2개의 곱한 값을 결과값에 % 1000000007 값을 결과값에 추가로 곱

     4. ProrityQueue의 사이즈가 1이 될 때 까지 1~3 반복

▶  처음 사이즈가 1로 입력 되면 1 출력

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	// 김xx 키보드 좋다. 없어지면 나야.
	// who are youuu
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
	
		// 테스트 케이스 입력 받고,
		int T = Integer.parseInt(bReader.readLine());
		
		for(int t = 1; t<= T; t++) {
			// 슬라임 갯수
			PriorityQueue<Long> qSlime =  new PriorityQueue<>();
			int nSlime = Integer.parseInt(bReader.readLine());
			StringTokenizer st = new StringTokenizer(bReader.readLine());
			for(int i = 0; i < nSlime; i++) {
				// 슬라임의 에너지 값을 넣어주자
				qSlime.add(Long.parseLong(st.nextToken()));
			}
			
			// 슬라임 에너지를 최소값을 갖는 2개까지 곱해주자
			// 우선 순위에서 2개씩 빼주면 계속 최소값만 곱해주므로
			// 최소로 에너지가 들게 된다.
			long lnResult = 1;
			while(qSlime.size() > 1) {
				long lnFirst = qSlime.poll();
				long lnSecond = qSlime.poll();
				long lnMul = (lnFirst * lnSecond) % 1000000007;
				
				lnResult *= lnMul;
				lnResult %= 1000000007;
				
				qSlime.add(lnFirst * lnSecond);
			}
			
			//if(lnResult != 1)
				
			
			bWriter.write(lnResult +"\n");
			bWriter.flush();
		}
		
		bWriter.close();
	}
}

---

Good Luck! (피드백 감사합니다!)