[우선순위 큐] BOJ 2014 소수의 곱

https://www.acmicpc.net/problem/2014

2014번: 소수의 곱

 

문제 해결 알고리즘

 

우선순위 큐를 이용하는 문제.

메모리 관리가 빡세다. 그냥 곱한 값들을 전부 우선순위 큐에 집어넣는 방식으로 하면 메모리 초과를 피할 수 없다.

 

우선순위 큐의 크기가 N보다 크고 최댓값보다 그 값이 크다면 건너뛰고 중복은 받지 않는 식으로 메모리 관리를 해주어야한다.

 

시행착오가 참 많았던 문제

 

소스 코드

 

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

int result_cnt = 0;
int K, N;
vector<ll> prime;
ll MAXvalue = 0;
map<ll, bool> visited;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> K >> N;
    
    priority_queue<ll , vector<ll>, greater<ll>> pq;

    for(int i=0;i<K;i++){
        ll n; cin >> n;
        pq.push(n);
        prime.push_back(n);
        visited[n] = true;
        MAXvalue = max(MAXvalue, n);
    }

    while(!pq.empty()){
        ll now = pq.top();
        pq.pop();
        result_cnt ++;
        
        if(result_cnt == N) {
            cout << now; break;
        }
        for(int i=0;i<K;i++){

            ll next = now * prime[i];

            if(N < pq.size() && next > MAXvalue) continue;
            if(!visited.count(next)){
                pq.push(next);
                visited[next] = true;
                MAXvalue = max(MAXvalue, next);
            }
        }
    }
}