[백준 2014] 소수의 곱

 

 

 

풀이

1. 입력한 소수들을 배열에 저장하고 우선순위큐(최소힙)에 담는다.

2. 우선순위큐의 top을 제거하고 top과 1번에서 저장한 배열의 각 인덱스를 곱하여 큐에 담는다.

3. 2번을 반복한다.

 

위 풀이대로 진행하면 중복된 수들도 큐에 담기게 되는데, 이 부분만 예외처리 하면

시간초과 없이 문제를 풀 수 있다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PriorityQueue<Long> pq = new PriorityQueue<Long>();
        
        int k = sc.nextInt();
        int n = sc.nextInt();
        int a[] = new int[k];
        for(int i=0; i<k; i++) {
            a[i] = sc.nextInt();
            pq.offer((long)a[i]);
        }
        for(int i=1; i<n; i++) {
            long top = pq.poll();
            for(int j=0; j<k; j++) {
                long push = top * a[j];
                pq.offer(push);
                if(top % a[j] == 0) break;
            }
            
        }
        System.out.println(pq.peek());
    }
}