[C++] 백준 2014 소수의 곱 [Gold1]

풀이

1. 우선순위 큐를 사용해서 문제를 해결할 수 있다.

2. 먼저, 주어진 소수를 저장하기 위한 벡터, 소수의 곱에 대해 이미 수행한 연산인지 확인하기 위한 체크 맵, 소수 곱을 저장하기 위한 우선순위 큐(greater)를 선언한다.

3. 입력을 받으면서 체크 맵에 표시해주고, 우선순위 큐에 집어 넣는다.

4. while loop를 돌면서 target 번째에 들어가면 답을 출력하고 break한다.

5. 이때, 우선순위 큐를 사용하기 때문에 top()에는 항상 최소값이 들어가 있다.

6. 즉, top()의 모든 경우를 출력할 경우 2, 3, 4, 5...순으로 나온다.

7. 1번째가 지나고 2번째에 top()을 했을 때 3이 나와야 하는 것은 pop을 통해 구현한다.

8. 이미 체크가 된 연산이거나, 우선순위 큐 크기가 target보다 큰데 현재 큐의 최대값 보다 큰 값일 경우 어차피 target값 보다 뒷쪽에 위치할 것이므로 push하지 않는다.  

9. push 할때마다 max 값을 업데이트 해주면 된다.

리뷰

1. 최소 힙에서 max값을 어떻게 구하지 생각했는데 그냥 push할 때 마다 max를 업데이트 하면 되는것이었다...ㅎ

2. 답이 INT_MAX보다 작다길래 int로 처리했는데, next를 구할 때 범위 초과로 문제가 되는 것 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;
using ll = long long;
int main()
{
    //freopen("2014.txt", "r", stdin);
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
    int n, target;
    cin >> n >> target;

    vector<int> v(n);
    priority_queue<ll, vector<ll>, greater<ll>> pq; 
    map<ll, bool> ch;
    ll max=0;
    for (int i=0; i<n; i++) {
        cin >> v[i];
        pq.push(v[i]);
        ch[v[i]] = 1;
        if (v[i] > max) max = v[i]; 
    }

    int cnt = 1;
    while (true) {
        ll num = pq.top();
        if (cnt == target) {
            cout << num << endl;
            break;
        }
        pq.pop();
        // pq size가 커지는 것 방지해야함
        for (int i=0; i<v.size(); i++) {
            ll next = num*v[i];
            
            if (ch.count(next)) continue;
            // 큐에 n개 넘게 있고 max 값보다 큰 값이 들어오려고 하면
            // 그 녀석은 어짜피 n번째 뒤의 값 : 패스
            if (pq.size() > target) {
                if (max <= next) {
                    continue;
                }
            }

            pq.push(next);
            ch[next] = true;
            if (next > max) max = next; 
        }
        cnt++;
    }

    return 0;
}