소수의 곱 C++ - 백준 2014

문제 접근

태그를 까기 전에는 어떤 트릭이 있을 줄 알았으나

우선순위 큐를 사용해 해결하는 문제였다.

이 문제의 핵심은 정수론적인 요소가 아니라

메모리 관리를 어떻게 하느냐였다.

소수의 곱으로 이루어진 수들을 우선순위 큐에서 관리하되

순서인 $N$을 넘기는 상황(우선순위 큐의 크기가 $N$보다 큰 경우)이 온다면

몇 가지 처리를 해주면 된다.

우선순위 큐의 크기가 $N$보다 크거나 같은 경우

현재 우선순위 큐의 최댓값보다 큰 값은 필요 없으므로 넣지 않고

최댓값보다 작은 값들은 필요하기에 이들만을 관리해준다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int k,n;
    cin >> k >> n;
    vector<ll> p(k);
    ll maxi=0;
    for(ll &t:p){
        cin >> t;
        maxi=max(maxi,t);
    }
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    unordered_set<ll> us;
    for(ll &t:p){
        pq.push(t);
        us.insert(t);
    }
    for(int i=1;i<n;i++){
        ll c=pq.top();
        pq.pop();
        for(ll &t:p){
            if(us.find(c*t)!=us.end()) continue;
            if(pq.size()>n && c*t>maxi) continue;
            maxi=max(maxi,c*t);
            us.insert(c*t);
            pq.push(c*t);
        }
    }
    cout << pq.top();
    return 0;
}