소수의 곱

김태성·2024년 4월 23일

알고리즘

목록 보기

12/30

곧있으면 플레 4가 된다.
시간이 없어서 정수론 문제를 깔짝여 봤는데 좋은 문제가 있었다.

https://www.acmicpc.net/problem/2014
소수의 곱

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 16816 4071 2851 23.874%
문제
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

소수와 각 소수의 곱을 정렬해서 N 번째 수를 찾는 간단한 문제이다.
시간제한 2초와 128MB라는 작은 메모리가 눈에 띈다.

알고리즘을 조금이라도 풀어봤다면 대충 사이즈가 나올건데
permutation을 쓰면 절대 못푸는 문제이다.
시간은 둘째치더라도 메모리가 터져버린다.

그래서 우리는 2가지 방법을 써야 된다.

import heapq
import sys


K , N = map(int,sys.stdin.readline().split())
prime = list(map(int,sys.stdin.readline().split()))
que = []
for i in prime:
    heapq.heappush(que,i)

count = 0
while count < N:
    a = heapq.heappop(que)
    for i in prime:
        heapq.heappush(que,i*a)
        if a%i == 0:
            break
    count += 1
    

print(a)