[백준] 2014번 - 소수의 곱

☞ 이 문제에서 가장 중요하게 생각 할 점은 배열에 저장되어 있는 소수들을 어떤 방식으로 곱해야 최대한 순서대로 저장시킬 수 있도록 해줘야 합니다. 그냥 순서대로 처음에 한개씩 다음에 2,2 2,3 2,4 2,5와 같이 2개씩 계산을 해서 우선순위 큐에 저장시켜주면 나중에는 같은 수로 곱하여도 차이가 많이 나기 때문입니다.(예를 들어 2*2*2 와 7*7*7의 차이가 어마어마하다.) 

따라서 여기서 우선순위 큐를 이용해 앞에 있는 수와 배열에 저장되어 있는 수들을 곱해 우선순위 큐에 저장시킨 후 다시 앞에 있는 수와 배열에 저장되어 있는 수들을 곱하는 방법을 반복한 후 N-1번째까지 반복 한 후 맨 앞에 있는 수가 정답이라는 것을 알 수 있었습니다.

여기서 2*2 를 하고 2*3 2*5를 가는 것보다 맨 앞에 있는 수인 4가 2*2이며 4*2를 하는 것이 2*5보다 작은 수가 나오는 것을 알 수 있어 더욱 효율적으로 우선순위큐를 만들 수 있습니다. 

 

※여기서 주의 할 점은 중복되는 수가 여러개 들어있을 수 있기 때문에 pq.top이 중복되지 않도록 아래와 같이 한번에 중복되는 수를 빼줄 수 있어야합니다. 

while (b == pq.top()) {
			pq.pop();
		}

 전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
using namespace std;

int K, N;

int main() {
	cin >> K >> N;
	priority_queue<int, vector<int>, greater<int>> pq;
	vector<int> minor;
	for (int i = 0; i < K; ++i) {
		int tmp;
		cin >> tmp;
		pq.push(tmp);
		minor.push_back(tmp);

	}
	int a = 0;
	long long b = 0;
	while (a < N-1) {
		a++;
		b = pq.top();
		for (int i = 0; i < K; ++i) {
			if( b*minor[i] < pow(2,31))
				pq.push(b*minor[i]);

		}
		while (b == pq.top()) {
			pq.pop();
		}
	}

	cout << pq.top();


}