소수의 곱

백준 2014번: 소수의 곱

아이디어

맨 처음 소수를 입력받을 때 최소 힙에 다 푸쉬한다. 그리고 하나씩 꺼내면서 입력받은 모든 소수와 한 번씩 곱하고, 그 값을 다시 푸쉬한다. 중복이 있을 수 있으므로 원소를 꺼낼 때 똑같은 원소를 다 꺼내고 N은 1만 감소시킨다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, K;
vector<int> num;
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> K >> N;
    int x;
    for (int i = 0; i < K; i++) {
        cin >> x;
        num.push_back(x);
        pq.push(x);
    }

    while (N>1) {
        int last = pq.top();
        while (!pq.empty() && pq.top() == last) {
            pq.pop();
        }
        N--;
        for (auto i = num.begin(); i != num.end(); i++) {
            if (1LL * last * (*i) > INT_MAX){
                continue;
            }
            else {
                pq.push(last * (*i));                
            }
        }     
    }
    cout << pq.top();
    return 0;
}

여담

첫 번째로 주의해야 할 점은 int 범위를 벗어나는지 확인하는 것이다.
두 번째로 주의해야 할 점은 N이나 K가 1일 때 예외처리를 잘 해주는 것이다.