BOJ#2014 소수의 곱

BOJ#2014 소수의 곱

* 문제

https://www.acmicpc.net/problem/2014

* 풀이

어려운 문제입니다.

K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자.

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

즉, 주어진 소수가 [2, 5, 7]일 때

2, 5, 7만을 약수로 갖는 숫자들 중 N 번째 숫자를 구하여라.

이 문제는 다음과 같은 알고리즘으로 해결을 할 수 있습니다.

1. 주어진 소수를 배열에 저장한다.

2. 주어진 소수를 PriorityQueue에 add 한다.

3. 아래 과정을 N-1 번 반복(loop)

- PriorityQueue에서 가장 작은 원소인 head를 꺼낸다.

- prime 배열의 각 원소에 대하여(loop)

- 꺼낸 head와 prime 배열의 각 원소를 곱한다.

- 구한 소수의 곱을 PriorityQueue에 add한다.

- 단, prime 원소가 head의 약수인 경우 다음 iteration으로 바로 넘어간다 (중복 방지)

4. PriorityQueue에서 head를 꺼내고 출력한다.(N번째 꺼내진 head가 정답이기 때문에)

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/985f7be9678fa9c33b644fffa7f678df670bf7a1/BOJ%232014/src/Main.java

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

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];

        PriorityQueue<Long> pq = new PriorityQueue<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {

            prime[i] = Long.parseLong(st.nextToken());
            pq.add(prime[i]);
        }

        long u = 0L;
        for (int i = 0; i < N - 1; i++) {

            u = pq.poll();

            for (int j = 0; j < K; j++) {

                pq.add(u * prime[j]);

                if (u % prime[j] == 0) break;
            }
        }

        System.out.println(pq.poll());
    }
}