백준 2014 소수의 곱 혼내주기

 

문제를 보고 pq로 뽑은 수에 모든 소수를 곱해서 다시 넣어야 겠다는 생각은 했는데, 계속 메모리 초과가 났다. 생각해보니 중복해서 들어가는 수랑 범위를 벗어난 수가 너무 많아보여서 set으로 중복을 제거하고 int 범위 벗어난 수는 다 거르고 넣었는데 메모리 초과가 나왔다. 아마 set에 int 범위 내의 숫자가 너무 많이 들어가서 그런 것 같다.

 

그래서 set을 없애고 중복을 거르기 위해서 이전에 뽑은 수와 현재 수가 같으면 스킵하는 방식으로 구현하니 메모리 100mb를 사용하고 통과했다. 다른 사람의 코드를 찾아보니 pq에 넣을 때 if(num % arr[i] == 0) break; 한줄만 넣어주면 애초에 중복되는 수를 넣지 않게 되어 메모리와 시간이 압도적으로 절약된다.

뭐랄까 하나만 알고 둘을 몰라서 못푼 것 같아 아쉽다.

 

 

 

비교샷 - 위의 결과가 아래 결과에서 if(num % arr[i] == 0) break;만 추가한 코드이다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

priority_queue<int> pq;
int arr[100];
int n, k;

void input() {
    fastio;
    cin >> n >> k;
    for(int i = 0; i < n; ++i) {
        cin >> arr[i];
        pq.push(-arr[i]);
    }
}

int main() {
    input();
    int cnt = 0, num;
    while(cnt < k) {
        num = -pq.top(); pq.pop();
        for(int i = 0; i < n; ++i) {
            long long next = 1LL*num * arr[i];
            if(next > __INT_MAX__) break;
            pq.push(-next);
            if(num % arr[i] == 0) break;
        }
        cnt++;
    }

    cout << num;
}