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

1. 문제

www.acmicpc.net/problem/14698

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

2. 접근방법

뭔 이상한 이름의 문제일까 했는데

 

문제도 조금 이상한거 같기도 하고 ;;

 

접근 방법은

1. pq를 이용해 현재 가장 작은 값 2개를 뽑은뒤 곱하고

2. 그 값을 result에 계속 곱한뒤 % 연산을 해주고

3. pq에 넣어주기

 

이것만 반복하다가

2개를 뽑아야하는데 한개만 남으면 안되니 while 종료

 

이유를 설명하자면

 

2 3 4 5의 슬라임이 있고

가장 큰수 부터 뽑는다고 가정하고 시뮬레이션을 돌려보자

 

que = 2, 3, 4, 5

num1 = 5

num2 = 4

result 5 * 4

-------------

que = 2, 3, 5*4

num1 = 5*4

num2 = 3

result = (5 * 4) * (5 * 4 * 3)

-------------

que = 2, 5*4*3

num1 = 5*4*3

num2 = 2

result = (5 * 4) * (5 * 4 * 3) * (5 * 4 * 3 * 2)

-------------

que = 5 * 4 * 3 * 2

que.size == 1 종료

 

무엇이 잘못되었는지 보이는가?

result는 작은 값이 되어야하는데 큰 값인 5가 여러번 중복되어 result에 곱해지고 있다.

 

다시 작은 수 부터 뽑는 것을 보여주면

que = 2, 3, 4, 5

num1 = 2

num2 = 3

result 2 * 3

-------------

que = 4, 5, 2*3

num1 = 4

num2 = 5

result = (2 * 3) * (4 * 5)

-------------

que = 2*3, 4*5

num1 = 2*3

num2 = 4*5

result = (2*3) * (4*5) * (2*3*4*5)

-------------

que = 2*3*4*5

que.size == 1 종료

 

이 알고리즘으로 풀이하면 답이 잘나온다

 

그리고 mod계산을 해줄 때

두 작은 값을 곱한 값은 항상 long보다 작다고 했으니 건들지 말고

result는 곱한 값들을 모두 곱하는 값이라 값이 오버플로가 일어날 수 있다.

 

그러므로 result에 mul을 곱할 때 mul에 mod계산 한 값을 result에 곱한 뒤 result에도 mod계산을 해주어야한다.

result = result *( mul % div ) % div;

 

만약 mul에 mod연산을 하면 값이 이상해지며

오버플로가 일어나 -값이 pq에 들어가게 되어 heap구조를 망쳐 시간초과가 나는 경우도 있는 것 같다.

 

만약 그래도 시간초과가 뜬다면

테스트케이스 T의 범위가 안정해져있고

그저 모든 테스트 케이스에 대한 N 의 총합이 1, 000, 000을 넘지 않음이 보장된다. 라고만 적혀있는데

T의 값이 커지면 println함수 호출이 너무 많아서 시간초과가 뜨게 되는 경우도 있다.

모든 결과값들을 stringbuilder 하나에 저장해서 

마지막에 한번만 출력해주도록 하자.

 

3. 자바 코드

package Gold;

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

public class P14698전생했더니슬라임연구자였던건에대하여 {
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder stb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		long div = 1000000007;
		for (int tc = 1; tc <= T; tc++) {
			PriorityQueue<Long> pq = new PriorityQueue<Long>();
			int N = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				pq.offer(Long.parseLong(st.nextToken()));
			}
			long result = 1;
			while (pq.size() != 1) {
				long mul = (pq.poll() * pq.poll());
				pq.offer(mul);
				result = result *( mul % div ) % div;
			}
			stb.append(result +"\n");
		}
		System.out.println(stb);
	}

}

4. 마치며

문제 해결은 어렵지 않게 해냈는데

세상 이상한 곳에 함정이 있어서 당황한 문제.