[백준/Python] 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번째 오는 것을 출력한다.

아 진짜 문해력에 문제가 있나

문제 자체가 너무 안읽힌다 책좀 읽어야할듯

뭐 문제를 3줄 요약하자면

4 19
2 3 5 7

K = 4 개의 소수 N = 19 순위 

arr = [2,3,5,7] 주어진 소수

1. 주어진 소수를 가지고 자유롭게 곱할 수 있는 모든 수를 오름차순 정렬

2. 정렬된 숫자 중 N번째 수를 출력

3. 끝 

이다. 여기서 핵심은 중복된 수가 정렬에 들어가지 않도록 하는것이 핵심이다

import heapq

k, n = map(int, input().split())
prime = list(map(int, input().split()))
h = prime[:]
#전체를 슬라이싱하는 것으로, 새로운 리스트를 생성

heapq.heapify(h)

for i in range(n):
    num = heapq.heappop(h)
    #가장 최소값을 뽑기
    for j in prime:
        heapq.heappush(h, num * j)
        if num % j == 0:
            #중복되는것을 방지
            break
print(num)

 

heapq 모듈을 사용한 최소힙을 이용해,

소수의 곱 중에서 작은 순서대로 하나씩 찾아내는 과정이 이번 알고리즘의 핵심이라고 볼 수 있다.

아래는 상세한 코드설명!

1. heapq.heappop(h)를 사용해서 h 리스트에서 가장 작은 값인 num을 가져온다. 이 값은 현재까지 구한 소수의 곱 중 가장 작은 값

2. prime 리스트에 있는 모든 소수 j에 대해서, num과 j의 곱을 heapq.heappush(h, num * j)를 사용해서 h 리스트에 추가한다. (여기서 자유롭게 곱을 만들어내는 과정~)

3. if num % j == 0:를 사용해서 num이 소수 j로 나누어 떨어지는 경우, 즉 num이 소수 j의 배수인 경우, break를 사용해서 이후의 소수 j에 대한 연산을 생략한다. (J를 추가하지 않고 다음 연산으로 넘어가기 위함)
이렇게 하면 h 리스트에는 항상 소수의 곱 중 가장 작은 값이 저장되게 된다.

4. 이를 n번 반복해서, n번째로 작은 소수의 곱을 구할 수 있다!

5. 마지막으로, print(num)을 사용해서 n번째로 작은 소수의 곱을 출력~