백준 2075: N번째 큰 수

문제 요약

K개의 소수가 있다. 이때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다. 소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자.

예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다.

K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 231보다 작은 자연수이다.

문제 분류

• 수학
• 자료 구조
• 정수론
• 우선순위 큐

문제 풀이

입력받은 소수들 사이의 곱들 중 n번째로 작은 수를 출력하는 우선순위 큐 문제다. 첫 번째로 입력받은 소수를 배열에 저장하고, 그 소수들을 우선순위 큐에 넣는다. 우선순위 큐는 최소 힙으로 구성하여 가장 낮은 값의 원소를 top으로 올린다. 그 후 이 큐에서 하나씩 빼면 되는데, 뺀 값에다가 배열의 소수들을 곱한 값들을 다시 큐에 넣으면 된다. 이 연산을 n번 해서 n번째로 작은 수를 찾으면 된다.

단, 이때 중복을 제거하기 위해 이전의 top을 저장해서, 현재와 이전의 값을 비교하는 작업을 했고, int범위를 초과하는 값을 걸러야 하기 때문에 long long의 변수를 선언하여 값을 비교하여 넣어주었다.

int 범위를 초과하는 것만 잘 걸러내주면 쉽게 풀 수 있다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
	int k, n, in, cnt = 1;
	priority_queue<int, vector<int>, greater<>> q;
	vector<long long> v;
	scanf("%d%d", &k, &n);
	for (int i = 0; i < k; i++) {
		scanf("%d", &in);
		q.push(in);
		v.push_back(in);
	}
	in = 1;
	while (cnt <= n) {
		auto t = q.top();
		q.pop();
		if (in == t) continue;
		for (auto& it : v) {
			long long temp = t * it;
			if (temp > 2147483647) break;
			q.push(temp);
		}
		in = t;
		cnt++;
	}
	cout << in;

	return 0;
}

후일담

여기서 큐를 long long으로 선언할 경우, 메모리 초과가 발생한다. 따라서 소수를 입력받은 배열인 vector를 long long으로 선언해야 한다.