백준 2014번 소수의 곱

< 백준 2014번 소수의 곱 - 마포 코딩박 >

사용한 알고리즘: priority_queue


 문제에서 주어진 소수들 곱으로 만들어지는 수 중 N번째로 작은 수를 구하는 문제입니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~10, 15~23)
 입력으로 주어지는 소수들을 작은 수 부터 위로 오도록 pq 를 만들어 저장합니다.
 또한 문제에서 주어지는 소수들을 따로 벡터를 만들어 저장해주었습니다.
 중복을 피하기 위해 set 을 써서 pq에 들어간 수를 기억해줬습니다.

(2) (코드 24~55)
 pq 에 저장된 수를 하나씩 꺼내어 N번째 수를 답으로 할 것입니다.
 pq의 top값은 가장작은 소수의 곱 (혹은 소수 자신) 입니다. 해당값에 주어진 소수들을 하나씩 곱해보며 다시 pq 안에 저장해주었습니다.
 이때 우리는 N번째 수를 원하므로, 저장한 pq 의 크기가 ( N-이미 본 개수 ) 보다 큰 경우, 만들어진 수가 pq 에 있는 가장 큰 값보다 큰 경우 답이 될 수 없으므로 무시합니다.