[BOJ] 백준 2014번 소수의 곱 (Java)

#2014 소수의 곱

난이도 : 골드 1

유형 : 소수 / 우선순위 큐

2014번: 소수의 곱

▸ 문제

K개의 소수가 있다. 이때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다. 소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자.

예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다.

K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 231보다 작은 자연수이다.

▸ 입력

첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 같은 자연수이다.

▸ 출력

첫째 줄에 문제에서 설명한 대로 소수의 곱을 나열했을 때, N번째 오는 것을 출력한다.

 

문제 풀이  

수열에 있는 수들끼리의 곱을 구하는 문제이다. 그래서 n번째 수가 나올 때까지 곱해주면 되는데 기본적으로 O(n*k) 이중포문 시간복잡도에 추가로 정렬하는데 걸리는 시간 O(logN), 중복 탐지하는 시간 O(n)이 걸리기 때문에 O(n^2)이 훨씬 초과하여 시간복잡도가 발생한다.

 

O(n*k)는 필수이고, 정렬 또한 우선순위 큐에 진행해주므로 필수이다. 그래서 중복 탐지하는 부분을 감소시켜줘야 한다. 이는 소수의 곱셈부분의 중복을 제거해주면 된다.

• 소수의 곱 prime * prime은 중복이 이중포문에서는 두번씩 연산이 이루어지기 때문에 소수가 자신이 포함된 합성수를 만나면 연산을 종료해준다.
• 소수들 끼리는 당연히 중복이 발생하므로 자신의 소수값을 만날 때 까지만 곱을 해준다.

	2	3	5	7
2	2x2	2x3	2x5	2x7
3	3x2	3x3	3x5	3x7
5	5x2	5x3	5x5	5x7
7	7x2	7x3	7x5	7x7

 

합성수의 경우도 마찬가지이다. (p x ... x q)로 이루어져있는 합성수도 자신을 포함한 소수를 만나면 뒤에 곱은 해주지 않아도 된다. 어차피 뒤에서 다른 소수가 자신의 턴이 올때 같은 연산을 해주기 때문이다.

• 예로 2x2x3 → 3x2x2 은 같은 연산인데 순서만 다를 뿐이다. 그래서 2가 추가되는 2x2x3연산은 패스하고 나중에 3이 추가되는3x2x2를 진행하게 해준다는 소리이다.

	2	3	5	7
4	2x2x2	2x2x3	2x2x5	2x2x7
6	2x3x2	2x3x3	2x3x5	2x3x7
8	2x2x2x2	2x2x2x3	2x2x2x5	2x2x2x7
9	3x3x2	3x3x3	3x3x5	3x3x7

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int k = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		
		long[] prime = new long[k];
		Queue<Long> q = new PriorityQueue<>();
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<k; i++) {
			prime[i] = Integer.parseInt(st.nextToken());
			q.add(prime[i]);
		}
		
		for(int i=0; i<n-1; i++) {
			long num = q.poll();
			
			for(int j=0; j<k; j++) {
				long mul = num * prime[j];
				q.add(mul);
				if(num%prime[j] ==0)break;
			}
		}
		System.out.println(q.poll());
	}
}