문제
풀이
수학, 우선순위 큐
위의 문제와 약간 비슷하다. 위의 문제는 전체 수 중에서 N번째로 큰 수를 찾는 문제로, 전체 수가 처음주터 주어진다. 이번 문제는 소수의 곱을 런타임에 구해야 한다.
N번째 소수의 곱을 찾는 과정은 다음과 같다.
- 오름차순 우선순위 큐를 만든다.
- 우선순위 큐의 top을 주어진 소수와 곱한다.
- 곱한 결과가 이전에 우선순위 큐에 들어오지 않았다면, 우선순위 큐에 넣는다.
- 이를 N번 반복한다.
- 이제 우선순위 큐의 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;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 5052: 전화번호 목록 (0) | 2024.03.21 |
---|---|
[백준][C++] 20920: 영단어 암기는 괴로워 (0) | 2024.03.20 |
[백준][C++] 1826: 연료 채우기 (0) | 2024.03.10 |
[백준][C++] 2696: 중앙값 구하기 (0) | 2024.03.07 |
[백준][C++] 1781: 컵라면 (0) | 2024.03.06 |