[BOJ] 2014 소수의 곱

import sys
import heapq
input = sys.stdin.readline

k, n = map(int, input().rstrip().split(" "))

arr = list(map(int, input().rstrip().split(" ")))
q = list(arr)
heapq.heapify(q)
head = None
for _ in range(n):
    head = heapq.heappop(q)
    for a in arr:
        heapq.heappush(q, head*a)
        if(head % a == 0):
            break

print(head)

문제

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

 

 

접근 방법이 쉽게 떠오르지 않았고, 시도했던 방법들이 제대로 동작하지 않아서 결국 풀이를 보게되었다.

 

핵심은 소수가 들어있는 pq랑 소수만있는 list가 있고

pq에서 1개씩 빼면서 list의 모든 요소와 곱하여 다시 pq에 넣어준다.

=> 메모리 초과 발생

중복을 제거하기 위해서

이때 서로서로의 원소의 곱으로 이루어져 있으므로, pq에서 뽑은 원소가 list의 원소의 배수라면 그 이상은 볼 필요가 없다.

왜냐하면 2x5나 5x2나 값이 똑같기 떄문이다.

누군가에겐 쉽게 떠올릴 수 있는 조건이었겠지만 나같은 경우는 쉽게 떠오르지 않았다.

꼭 기억하자.