[백준][2014] 소수의 곱 (이해 안가는부분이 있음)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	7158	1538	1078	22.154%

문제

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번째 오는 것을 출력한다.

예제 입력

4 19
2 3 5 7

예제 출력

27

소스

package bj;

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 bj2014 {

    public static int K; // 1<= K <=100
    public static int N; // 1<= N <=100000
    public static long arr[];
    public static PriorityQueue<Long> pq;

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        System.setIn(new FileInputStream("C://sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = 1;
        for (int tc = 1; tc <= T; tc++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());

            arr = new long[K];
            pq = new PriorityQueue<Long>();

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < K; i++) {
                arr[i] = Long.parseLong(st.nextToken());
                pq.add(arr[i]);
            }

            long result = search();

            bw.flush();
            bw.write(result + "\n");

        }
        bw.close();

    }

    public static long search() {

        long head = 0;
        for (int i = 0; i < N; i++) {
            head = pq.poll();
            for (int j = 0; j < K; j++) {
                pq.add(head * arr[j]);
                if (head % arr[j] == 0) {
                    break;
                }
            }
        }

        return head;

    }

}

풀이

1. 우선순위 큐를 정의하고, 최초의 소수 2,3,5,7을 넣는다.
2. 우선순위 큐에서 하나를 뺀다(최소값) 그리고 최초의 소수 2,3,5,7을 곱해서 다시 큐에 넣는다.
3. 1~2번을 N번 반복하면 N번째 큰 수가 나온다.
4. 중복을 방지하기 위해 큐에서 뺀 숫자의 약수가 소수 중에 있다면 더이상 곱하는걸 멈춘다.

의문점

• 풀이의 4번이 아직도 이해가 안간다. 아무도 이부분에 대해 설명해주지 않는다