[python] 백준 - 2014. 소수의 곱

🤔문제 해결

• G2 | 수학, 우선순위 큐

DP로 구해보려고 했지만 역시 아니었다. 2**31 길이의 배열은 좀 아닌거 같다.

어려워서 알고리즘 분류를 보니 우선순위 큐로 해결하는 문제였다.

 

우선순위큐는 큐 안에 있는 값들 중 최소 값을 반환할 수 있다.

파이썬에서는 힙큐를 불러와서 사용하고 힙큐는 최소힙 기반으로 되어있다.

 

해결방법은

1. 최초 힙큐에 주어진 소수를 넣는다.
2. 힙큐에서 숫자를 하나씩 꺼내면서 주어진 소수들을 곱해서 힙큐에 넣는다.
   
   1. (이 때 꺼내는 횟수가 소수의 곱들 중에서 N번째 수이다)
3. 하지만 이렇게 되면 중복이 발생한다. ( 2*3 이나 3*2 )
4. 3*2는 되지만 2*3은 안된다는 식으로 힙큐에서 꺼낸 수가 소수로 나누어 떨어지면 그 다음 소수는 건너뛴다.
5. 결과는 아래와 같다

 

 

💻소스 코드

 import heapq

if __name__ == '__main__':
    K, N = map(int, input().split())
    prime = list(map(int, input().split()))

    pq = []  # 곱한 값이 들어갈 리스트 (우선순위 큐)
    for num in prime:
        heapq.heappush(pq, num)

    for i in range(N):  # 큐에서 N번 빼면 그 값이 N번째 값이다. (우선순위 큐)
        num = heapq.heappop(pq)
        for j in range(K):  # 뺸 값에 소수를 곱해서 새로운 값을 만든다.
            new_num = num * prime[j]
            heapq.heappush(pq, new_num)

            if num % prime[j] == 0:  # 2 X 3은 되지만 3 X 2는 안되는 느낌으로 중복제거
                break
    else:
        print(num)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

2014번: 소수의 곱