[백준/2014] 소수의 곱 (Python)

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

2014번: 소수의 곱

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:36:53

 

---

 

문제 설명

 

 

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

 

 

---

 

풀이

 

소수의 곱을 나타낼 때, 어떻게 나타내 볼 수 있을까? 우선 제일 작은 결과를 뽑아 모든 소수와 곱해보고, 두 번째로 작은 결과를 뽑아 모든 소수를 곱해보고... 이런 식으로 러프하게 생각해 볼 수 있다. 또한 동시에, 이 곱셈 결과들은 항상 정렬을 유지해야 한다. 즉 우선순위 큐를 사용해 봄직하다. O(NlogN)의 시간복잡도는 충분히 문제 조건을 충족시킨다.

 

문제는 중복되는 수를 처리하는 것이다. 이를테면, 6은 2*3 = 3*2의 두 가지 경우가 생기며, 12는 3*2*2 = 2*3*2 = 2*2*3의 세 가지 경우가 생긴다. 즉 어느 한 가지 경우의 수만을 고려해야만 정상적인 답을 출력할 수 있다. i번째 결과를 num[i]라 두고, num[i]의 소인수를 (n[1], n[2], ... n[m])이라고 두자. (n[1] < n[2] < ... < n[m], 주어진 소수집합의 부분집합)

 

이 때, 모든 소수를 num[i]에 곱셈을 수행한다면, n[1]까지만을 곱셈해주면 중복을 피할 수 있다. 즉 가장 작은 소인수 이하의 소수만을 곱셈하도록 하면, 곱셈식이 내림차순으로 진행된다. 6 = 3*2, 12 = 3*2*2의 단 한 가지 경우만이 존재하게 되는 셈이다. 이 방식 역시 생각해보면 매우 쉬운 방식이 존재하는데, num[i]와 해당 소수의 나머지가 0이 되는 순간(즉 최초의 소인수 n[1]이 나타나는 순간)에 곱셈을 중지하면 된다.

 

풀이 코드

from heapq import *

K, N = map(int, input().split())
prime_num = list(map(int, input().split()))
q = prime_num[:]
heapify(q)

for _ in range(N) :
  num = heappop(q)
  for p in prime_num :
    heappush(q, num*p)
    if num % p == 0 :
      break
      
print(num)

풀이 완료!