[백준 2014번] 소수의 곱

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

2014번: 소수의 곱

<문제 풀이> 우선순위 큐

각 소수에 대해서 K개의 소수를 계속 곱해 나가면 모든 소수의 곱을 구할 수 있는데, 여기서 중복 없이 구해서 최소 힙에 넣고 N 번째로 작은 수를 구하면 됩니다.

 

모든 소수의 곱을 구할 때 중복을 제거하는 방법은 가장 마지막에 곱해졌던 소수보다 작거나 같은 소수까지만 곱해주면 됩니다.

예를 들어

마지막에 곱해진 소수 2, 3, 5가 있을 때 각 소수에 K개의 소수인 2, 3, 5를 곱했을 때  2 * 3, 2 * 5, 3 * 5는 모두 중복입니다. 마지막에 곱해지는 수보다 큰 수를 곱하는 것은 어차피 뒤에서 한 번 더 곱해지기 때문에 더 곱해줄 필요가 없습니다.
2 x 2 | 3 x 2 | 5 x 2
2 x 3 | 3 x 3 | 5 x 3

2 x 5 | 3 x 5 | 5 x 5

 

<C++ 소스 코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
#define MAX (long long)2 << 31
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int k, n;
    cin >> k >> n;
    priority_queue<long long, vector<long long>, greater<long long> > pq;
    vector<int> plist;
    for (int i = 0; i < k; i++) {
        int p;
        cin >> p;
        plist.push_back(p);
        pq.push(p);
    }
    int cnt = 0;
    long long cur = 0;
    while (n--) {
        cur = pq.top();
        pq.pop();
        for (auto& p : plist) {
            if ((long long)p * cur >= MAX)break;
            pq.push(p * cur);
            if (cur % p == 0) break; //중복 제거
        }
    }
    cout<<cur;
 
}