[JAVA] 백준 2014번 소수의 곱

[HAVE TO DO]

STUDYING : JAVA

---

문제링크 : https://www.acmicpc.net/problem/2014

 

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

public class Main {
	
	static int K, N;
	static int[] nums;
	static PriorityQueue<Long> pq = new PriorityQueue<>();
	static long head = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		nums = new int[K];
		st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < K; i++) {			
			nums[i] = Integer.parseInt(st.nextToken());
			pq.add((long)nums[i]);
		}
		
		
		for (int i = 0; i < N - 1; i++) {
			head = pq.poll();
			
			for (int j = 0; j < K; j++) {
				long num = head * nums[j];
				pq.add(num);
				
				if(head % nums[j] == 0) break;
			}
		}
		
		head = pq.poll();
		
		bw.write(String.valueOf(head));		
		
		br.close();
		bw.flush();
		bw.close();		
	}

}

중복을 제거하기 위해

head % nums[j] == 0 의 경우 break 건다는게 잘 이해가 안 갔는데 직접 써보니까 이해가 갔다.

 

소수가 2 3 7 일 경우, 추가하는 숫자들은

첫 번째(2) : 4

두 번째(3) : 6 9

세 번째(4) : 8

네 번째(6) : 12

다섯 번째(7) : 14 21 49

여섯 번째(8) : 16

...

모든 자연수는 소수 또는 소수들의 곱이기 때문에 어떻게든 나올 숫자는 나오게 되어 있다. 그렇기에 중복 처리는 나누어떨어지면 우선 빠져나오고 다음 숫자를 뽑아 거기에 소수를 곱해주며 계속 도는 것으로 해결 가능하다. (36의 경우 12 * 3 으로 먼저 구할 수도 있지만 나중에 뽑힐 18 * 2로도 구할 수 있다. 12*3으로 먼저 36을 구하면 뒤에서 18이 뽑혔을 때 아무것도 곱하지 말고 넘어가야 하는데 그 조건을 처리하는게 더 귀찮을 것 같았다.)

 

우선순위 큐(Priority Queue)를 사용하면 알아서 작은 수부터 뽑힌다.