소수의 곱

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

🤔문제 해결 G2 | 수학, 우선순위 큐 DP로 구해보려고 했지만 역시 아니었다. 2**31 길이의 배열은 좀 아닌거 같다. 어려워서 알고리즘 분류를 보니 우선순위 큐로 해결하는 문제였다. 우선순위큐는 큐 안에 있는 값들 중 최소 값을 반환할 수 있다. 파이썬에서는 힙큐를 불러와서 사용하고 힙큐는 최소힙 기반으로 되어있다. 해결방법은 최초 힙큐에 주어진 소수를 넣는다. 힙큐에서 숫자를 하나씩 꺼내면서 주어진 소수들을 곱해서 힙큐에 넣는다. (이 때 꺼내는 횟수가 소수의 곱들 중에서 N번째 수이다) 하지만 이렇게 되면 중복이 발생한다. ( 2*3 이나 3*2 ) 3*2는 되지만 2*3은 안된다는 식으로 힙큐에서 꺼낸 수가 소수로 나누어 떨어지면 그 다음 소수는 건너뛴다. 결과는 아래와 같다 💻소스 코드 i..