BOJ 2014 소수의 곱

문제 : BOJ 2014 소수의 곱

최소힙을 이용해서 항상 최소값을 구해내고,
갱신되는 소수의 곱이 항상 최소가 되도록 유지해야한다.

순회를 반복하며 최소힙 내에 새로운 연산 결과를 push 하고
결국 가장 작은 값을 중복없이 힙에 넣어줄 수 있는 방법을 생각해 내지 못하였다.

풀이

한시간 반 정도 고민하다가 다른 사람들의 풀이를 보고 이해했다.

방법은 크게 세가지 순서로 구분된다.

첫번째로, 최소힙의 성질을 이용해서 n번째 순회때 n번째 수를 pop()할 수 있도록 구현한다.

두번째는 매 순회때 마다 나온 최소값과 입력받은 소수들을 순회하며
새로운 최소값을 만들어 push() 하는데,

세번째로, 이 때 중복된 값이 저장되지 않게 하기 위한 조건이 필요하다.

import sys
import heapq

k, n = map(int, input().split())
pnum = list(map(int, input().split()))

heap = []
for p in pnum:
    heapq.heappush(heap, p)

입력받은 소수는 리스트로 유지하고,
힙에도 이 소수들을 push()해준 상태에서 시작한다.

전체 n번을 순회하면서 최소값을 갱신해주기 위해
첫번째와 두번째를 먼저 구현하면, 아래와 같다.

for i in range(n):
    num = heapq.heappop(heap)
    for p in pnum:
        tmp = num * p
        heapq.heappush(heap, tmp)

힙에 저장된 최소값을 꺼내고
그 최소값과 입력된 모든 소수들을 한번씩 곱해준 결과를 다시 힙에 저장한다.

이 과정에서 발생하는 문제는, 중복되는 숫자가 만들어 진다는 것이다.
입력받은 소수에 2와 3이 포함되어 있다면
i==0 일 때 만들어지는 6 (2 $\times$ 3)과
i==1 일 때 만들어지는 6 (3 $\times$ 2) 두개가 들어간다.

이런 방식으로 만들어지는 숫자는 아래 표처럼 표현할 수 있다.

\	2	3	5	7
2	2 $\times$ 2	2 $\times$ 3	2 $\times$ 5	2 $\times$ 7
3	3 $\times$ 2	3 $\times$ 3	3 $\times$ 5	3 $\times$ 7
5	5 $\times$ 2	5 $\times$ 3	5 $\times$ 5	5 $\times$ 7
7	7 $\times$ 2	7 $\times$ 3	7 $\times$ 5	7 $\times$ 7

대각선의 양 옆으로 중복되는 숫자가 나타나는것을 볼 수 있다.

결국 전체 과정에서 한쪽 절반의 계산은 진행되지 않아야 하고

이는 현재 순회중인 최소값이 어떤 소수로 나누어떨어지면,
그 이후의 연산은 진행하지 말아야 한다는 이야기와 같다.

[ 전체 코드 ]

import sys
import heapq

k, n = map(int, input().split())
pnum = list(map(int, input().split()))

heap = []
for p in pnum:
    heapq.heappush(heap, p)

for i in range(n):
    num = heapq.heappop(heap)
    for p in pnum:
        tmp = num * p
        heapq.heappush(heap, tmp)
        if num % p == 0:
            break

print(num)