[PS] 백준 - 소수의 곱 (2014번)

DevSWYoon·2022년 12월 15일

Problem Solving algorithm priority queue 백준

백준 문제풀이

목록 보기

2/7

0. 문제 소개

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

주어지는 K 개의 소수에 대해 소수들 간의 곱을 오름차순으로 나타내었을 때, N 번째에 해당하는 수를 출력하는 문제이다. (K = [1,100], N = [1,100000], 주어지는 소수 = [2,541], 정답 = [2,2^31) )

I. 접근

1. 에라토스테네스의 체

처음엔 소수라는 단어만 보고 에라토스테네스의 체를 이용하고자 하였으나, 에라토스테네스의 체는 주어진 소수간의 곱만 골라낼 수 없다.

2. 우선순위 큐

임의의 자연수 i 에 대해, 곱들 중 i 번째 수에 주어진 모든 소수를 곱한 결과값들을 기존의 곱들을 원소로 하는 집합에 넣어 최소값을 구하면, 그 최소값이 i+1 번째 수가 된다. (단, 최소값이 i 번째 수와 같지 않아야 한다.)

위와같이 어떠한 집합에 새로운 원소들을 추가하고, 그 중 최소값을 구하는 것을 가장 효율적으로 수행할 수 있는 자료구조는 단연 우선순위 큐일 것이다.

II. 코드 작성

I-2. 에서 했던 접근을 그대로 사용하여 코드를 작성해도 무리가 없어 보인다.
단, 32비트 Integer 자료형을 사용한다면, Overflow가 발생하지 않도록 주의해야 할 것이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long  ll;

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int N, K;
    vector<int> prime_nums;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    cin>>K>>N;
    prime_nums.resize(K);
    
    for(int i = 0; i < K; ++i)
    {
        cin>>prime_nums[i];
        pq.push(prime_nums[i]);
    }
    
    int before_val = -1;
    int cnt = 0;
    
    int ret = -1;
    
    while(cnt < N)
    {
        int cur = pq.top();
        
        pq.pop();
        
        if(before_val == cur) continue;
        
        before_val = cur;
        
        for(int i = 0; i < K; ++i)
        {
            if((ll) cur * (ll) prime_nums[i] > INT32_MAX) break;
            pq.push(cur * prime_nums[i]);
        }
        
        ret = cur;
        
        cnt++;
    }
    
    cout<<ret;
    
    return 0;
}