[백준][C++] 2014: 소수의 곱

문제

2014번: 소수의 곱

풀이

수학, 우선순위 큐

 

[백준][C++] 2075: N번째 큰 수

위의 문제와 약간 비슷하다. 위의 문제는 전체 수 중에서 N번째로 큰 수를 찾는 문제로, 전체 수가 처음주터 주어진다. 이번 문제는 소수의 곱을 런타임에 구해야 한다. 

 

N번째 소수의 곱을 찾는 과정은 다음과 같다. 

1. 오름차순 우선순위 큐를 만든다. 
2. 우선순위 큐의 top을 주어진 소수와 곱한다.
3. 곱한 결과가 이전에 우선순위 큐에 들어오지 않았다면, 우선순위 큐에 넣는다. 
4. 이를 N번 반복한다. 
5. 이제 우선순위 큐의 top에 N번째 큰 수가 위치하게 된다.

프로세스는 위와 같지만 이렇게 하면, 메모리 초과가 발생한다. 여기서 우선순위 큐에 들어가는 값들을 제한해야 하는데 이는 다음과 같다.

• 우선순위 큐의 size가 N보다 크면서, 현재 곱한 결과가 우선순위 큐에 들어가 있는 값의 최대값 이상이라면 우선순위 큐에 넣지 않는다. 

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

priority_queue<long long, vector<long long>, greater<long long>> pq;
vector<int> primes;
map<long long, bool> visited;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int K, N;
    cin >> K >> N;

    for (int i = 0; i < K; ++i)
    {
        int prime;
        cin >> prime;

        primes.push_back(prime);
    }
    pq.push(1);
    visited[1] = true;

    long long maxi = 0;

    while (N--)
    {
        long long current_mini = pq.top();
        pq.pop();

        for (int prime : primes)
        {
            long long current_value = current_mini * prime;

            if (visited.find(current_value) != visited.end())
            {
                continue;
            }

            if (pq.size() > N && current_value >= maxi)
            {
                continue;
            }

            pq.push(current_value);
            visited[current_value] = true;

            maxi = max(maxi, current_value);
        }
    }

    cout << pq.top();

    return 0;
}