[골드 1] 백준 2014 - 소수의 곱 (파이썬)

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

풀이

• 우선순위 큐를 사용해 가장 작은 수부터 하나씩 꺼낸다.
• 꺼낸 수에 소수 p를 곱해서 새로운 수를 힙에 추가한다.
• 단, 중복된 수가 너무 많이 생길 수 있으므로 최적화를 진행한다.

if v % p == 0:
    break

이미 v가 p로 나누어 떨어진다면, 앞으로 곱할 수들은 p가 가장 작은 소인수이므로, 나머지 소수들과 곱하면 중복된 수가 생성된다.

예를 들어 2 * 3과 3 * 2는 같은 수 6이 두번 생성된다.

따라서 가장 작은 소인수만 사용해서 확장하고 나머지는 무시해서 중복을 방지한다.

코드

# 백준 2014 - 소수의 곱
# 분류 - 수학
 
import heapq
K, N = map(int, input().split())
P = list(map(int, input().split()))
 
heap = []
for p in P :
    heapq.heappush(heap, p)
 
v = 0
for _ in range(N) :
    v = heapq.heappop(heap)
 
    for p in P :
        if v * p >= 2 ** 31 :
            break
        heapq.heappush(heap, v * p)
        if v % p == 0 :
            break
 
print(v)