백준 2014 - 소수의 곱 (C++)

문제

• 문제 링크

  
   BOJ 2014 - 소수의 곱 
  

• 문제 요약

$K$개의 소수에서 몇 개의 소수들을 곱하여 나열할 수 있다.
이 수열의 $N$번째 수를 구해보자.

• 제한

TL : $2$ sec, ML : $128$ MB




$1 ≤ K ≤ 100$

$1 ≤ N ≤ 100,000$

알고리즘 분류

• 자료 구조(data structures)
• 우선순위 큐(priority_queue)
• 수학(math)
• 정수론(number_theory)

풀이

우선순위 큐를 활용하는, 웰노운스러운 문제다.

매 사이클마다 가장 작은 수( $Q.top()$ )를 가지고 입력받은 수들과 곱해주면 된다.
그렇게 뚝딱 짜고 냈더니 처음에 $MLE$ 를 한 번 맞았다.

저번에 비슷한 문제를 풀었을 땐 $K ≤ 10$ 에 $N ≤ 200,000$ 의 상한이어서 그런지 비슷하게 짜도 통과 했었는데,
아무래도 메모리 제한과 $K$의 상한이 꽤 영향을 끼쳤나 보다.
이는 중간 과정에 다음의 조건을 추가해 해결했다.

• 현재 큐의 사이즈가 $N$보다 크고
• 큐에 들어있는 수의 최댓값이 $t * a[i]$ 보다 작거나 같다면 $continue$

필요한 만큼만 큐에서 들고 있을 수 있도록 하는 문장이다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
priority_queue <ll> Q;
unordered_set <ll> S;
ll k, n, m, a[101];
 
int main()
{
    cin >> k >> n; Q.push(-1);
    for (ll i{}; i < k; cin >> a[i++]);
    while (n--)
    {
        ll t(-Q.top()); Q.pop();
        for (ll i{}; i < k; i++)
            if (ll x(t * a[i]); !S.count(x) && (!(Q.size() > n && x >= m)))
            {
                Q.push(-x), S.insert(x);
                m = max(m, x);
            }
    }
    cout << -Q.top();
}

comment

끝