백준 2014번 소수의 곱

< 백준 2014번 소수의 곱 - 마포 코딩박 >

사용한 알고리즘: priority_queue


 문제에서 주어진 소수들 곱으로 만들어지는 수 중 N번째로 작은 수를 구하는 문제입니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~10, 15~23)
 입력으로 주어지는 소수들을 작은 수 부터 위로 오도록 pq 를 만들어 저장합니다.
 또한 문제에서 주어지는 소수들을 따로 벡터를 만들어 저장해주었습니다.
 중복을 피하기 위해 set 을 써서 pq에 들어간 수를 기억해줬습니다.

(2) (코드 24~55)
 pq 에 저장된 수를 하나씩 꺼내어 N번째 수를 답으로 할 것입니다.
 pq의 top값은 가장작은 소수의 곱 (혹은 소수 자신) 입니다. 해당값에 주어진 소수들을 하나씩 곱해보며 다시 pq 안에 저장해주었습니다.
 이때 우리는 N번째 수를 원하므로, 저장한 pq 의 크기가 ( N-이미 본 개수 ) 보다 큰 경우, 만들어진 수가 pq 에 있는 가장 큰 값보다 큰 경우 답이 될 수 없으므로 무시합니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const ll INF = INT_MAX;
	int K, N, cnt;
	vector<int> Prime;
	priority_queue<int, vector<int>, greater<int>> Q;
	set<int> visited;
	int max_value;
	int ans;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> K >> N;
	for (int i = 0; i < K; ++i){
	int a;
	cin >> a;
	// 소수 저장
	Prime.push_back(a);
	Q.push(a);
	// max_value: Q안의 숫자중 최대 수
	if(i==K-1) max_value = a;
	}
	while(1){
	// temp*P 가 long long 범위일 수 있으니 일단 long long으로 들고감
	ll temp = (ll)Q.top();
	Q.pop();
	// 제일 작은게 위에 있을거임.
	if(ans!=temp){
	// 몇번째 작은 소수곱인지 체크
	ans = temp;
	cnt++;
	// N번째이면 출력
	if(cnt==N){
	cout << ans << '\n';
	break;
	}
	}
	for(auto P: Prime){
	// Q에 충분히 들어있을때(N-cnt 개만 있으면 됨), Q안의 최대값보다 큰 값들은 볼필요 X
	// 소수는 정렬 되어 있어, 뒤를 계산 할수록 더 커지니 break
	if(Q.size() >= N-cnt && temp*(ll)P >= max_value) break;
	// 답은 INF 보다 작다고 문제에 명시
	if(temp*(ll)P>INF) break;
	// 계산위해 int 전환
	int tt = (int)temp*P;
	// Q에 넣기 전 중복 체크
	if(!visited.count(tt)){
	visited.insert(tt);
	Q.push(tt);
	// Q 안에 들은 최대값
	max_value = max(max_value , tt);
	}
	}
	}
	return 0;
	}

view raw BOJ 2014.cpp hosted with ❤ by GitHub