[Baekjoon] 2014번 : 소수의 곱

1. 문제

https://www.acmicpc.net/problem/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번째 오는 것을 출력한다.

// 예제 입력 1
4 19
2 3 5 7

// 예제 출력 1
27

2. 핵심 아이디어

• heapq 사용
• 중복 없이 최소 힙에 넣고 n번째로 작은 수를 구함
• pypy3으로 제출

3. Python 문제풀이

import sys
import heapq
import copy
input = sys.stdin.readline

k, n = map(int, input().split())
arr = list(map(int, input().split()))

lst, ck = copy.deepcopy(arr), set()

heapq.heapify(lst)
ith = 0

while ith < n :
  mn = heapq.heappop(lst)
  if mn in ck :
    continue
  ith += 1
  ck.add(mn)
  for i in arr :
    heapq.heappush(lst, mn * i)

print(mn)

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int k = Integer.parseInt(st.nextToken());
    int n = Integer.parseInt(st.nextToken());
    long[] arr = new long[k];

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

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

    long ans = 0;

    while (n-- > 0) {
      ans = pq.poll();
      for (int i=0; i<k; i++) {
        if ((ans * arr[i]) >= ((long) 2 << 30)) {
            break;
        }
        pq.offer(ans * arr[i]);
        if (ans % arr[i] == 0) {
          break;
        }
      }
    }
    bw.write(ans + "\n");
    bw.flush();
    bw.close();
    br.close();
  }
}