백준 2014 : 소수의 곱 c++

2014번: 소수의 곱 (acmicpc.net)

2014번: 소수의 곱

백준 2014번 소수의 곱 (tistory.com)

백준 2014번 소수의 곱

해당 블로그를 참고했습니다.

 

풀이
1. 현재 가장 작은 수에 소수들을 모두 곱하여 우선순위큐에 삽입
2. 우선순위큐의 크기가 n보다 크거나 같고 큐안의 최대값보다 현재 곱이 클 경우 더 이상 삽입하지 않음
3. 중복 삽입을 제외하기 위해 set 사용

 

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

set<ll> check;
int main() {
    init();
    int k, n; cin >> k >> n;
    int max_n = n;
    vector<ll> v(k);
    priority_queue<ll> pq;

    for (int i = 0; i < k; i++)
        cin >> v[i];

    int mx = 0;

    pq.push(-1);

    while (n--) {
        ll temp = -pq.top();
        pq.pop();
        for (int i = 0; i < k; i++) {
            ll next = temp * v[i];
            if (mx <= next && pq.size() >= max_n)
                break;

            if (!check.count(next)) {
                check.insert(next);
                pq.push(-next);
                mx = max(next, ll(mx));
            }
        }
    }
    cout << -pq.top();
}