[c++] 백준 - 2014 소수의 곱 (우선순위 큐)

1. 문제

2. 입출력 및 예제

---

3. 문제 해설

우선순위 큐를 이용해 푸는 문제였다. 처음에는 아무런 생각도 하지 못하고 있다가 알고리즘 분류를 봤더니 우선순위 큐 분류에 있는 것을 확인한 후 풀 수 있었던 문제이다. 이 문제의 핵심아이디어는 다음과 같다. 

 

우선 주어진 수들을 모두 우선순위 큐 안에 집어 넣는다. 우리는 오름차순으로 수를 구해야하므로 우선순위 큐는 오름차순으로 선언해준다.

#include <vector>
#include <queue>
#define ll long long
priority_queue<ll , vector<ll>, greater<>> pq;

그 후 오름차순 우선 순위 큐에 집어넣고 pq.top()에 해당하는 값들을 계속 원래 입력으로 받았던 소수에 곱을 해주면서 다시 우선순위큐에 집어넣어주면 그 횟수를 N번 반복했을 때의 pq의 top이 정답이 된다. 

 

4 5

2 3 5 7의 경우를 살펴보면

pq.top() = 2이므로

2*2 = 4,

2*3 = 6,

2*5 = 10,

2*7 = 14가 추가되어 우선순위 큐의 모습은 다음과 같이 될 것이다. 

2 3 4 5 6 7 10

2를 pop해준다.

 

pq.top() = 3이므로

3*2 = 6 이미 나왔다.

3*3 = 9

3*5 = 15

3*7 = 21

가 추가되어 우선순위 큐의 모습은 다음과 같이 된다. 

3 4 5 6 7 9 15 21

3을 pop해준다. 

 

pq.top() = 4이므로

4*2 = 8

4*3 = 12

4*5 = 20

4*7 = 28

이 추가되어 우선 순위 큐의 모습은 다음과 같이 된다. 

4 5 6 7 8 9 12 15 20 21 28

 

그런데 생각을 해보면 앞서도 이미 계산이 된 수에 대해서는 continue를 해줘야하고 생각해보면 5번째 큰 수를 구하는데 pq.size()가 5가 넘고 그 pq안에 들어있는 가장 큰 수보다 더 큰 새로운 수가 들어온다면 이 수는 무조건 5번째보단 큰 수일 것이기 때문에 pq안에 추가해 줄 필요가 없다. 

따라서 나는 방문 체크를 map을 이용해서 해주고 

pq안의 최댓값을 갱신해가면서 pq.size() > N인데 새로 들어온 수가 기존의 최댓값보다 크다면 집어넣지 않고 continue해주는 방법을 사용했다. 

 

이 방법들을 사용하지 않으면 아마 시간초과나 메모리 초과가 날 것이다. 

 

또한 이 문제를 풀며 map을 좀 더 깊게 알게 되었는데 map은 그 주소에 방문만 하여도 메모리가 할당되기 때문에 

if(map[next]) continue;

와 같이 방문 체크를 하면 map[next]값이 없어도 메모리가 할당되어 메모리 낭비가 심하게 된다. 따라서 위와 같이 체크하면 메모리 초과가 나고 map의 다른 method를 사용하여 체크해줘야한다.

if(map.count(next)) continue;

---

4. 코드

#pragma warning (disable :4996)

#include <cstdio>
#include <queue>
#include <map>
#include <algorithm>
#include <vector>
#define ll long long 
using namespace std;

int K, N;
ll primeNum[101];
int cnt;
priority_queue<ll, vector<ll>, greater<ll>> pq;
map<ll, bool> mp;
void input() {
	scanf("%d %d", &K, &N);
	for (int i = 0; i < K; i++) {
		scanf("%lld", &primeNum[i]);
	}
}


void sol() {
	ll mx = 0;
	for (int i = 0; i < K; i++) {
		mp[primeNum[i]] = 1; // 방문 표시
		pq.push(primeNum[i]); // pq에 값을 넣어준다.
		mx = max(mx, primeNum[i]);
	}
	
	while (cnt < N-1) {
		ll curr = pq.top(); pq.pop();
		cnt++;
		//printf("pq.top() : %d\n", -pq.top());
		for (int i = 0; i < K; i++) {
			ll next = curr * primeNum[i];
			if (mp.count(next)) continue;
			if (pq.size() > N) {
				if (mx <= next) continue;
			}
			//printf("curr * primeNum[%d] : %d\n", i, curr * primeNum[i]);
			mp[next] = true; // 방문 표시
			pq.push(next);
			mx = max(mx, next);
		}

	}
	printf("%lld\n", pq.top());
}
int main() {
	input();
	sol();

	return 0;
}

수 많은 흔적들...