BOJ 2014 소수의 곱

www.acmicpc.net/problem/2014

2014번: 소수의 곱

 

처음에는

arr[i] = i번째 합성수

를 사용하여 값을 저장하려고 했다.

하지만, i+1번째 합성수를 구하기 위해서는 1~i번째 합성수와 단위소수들을 각각 곱한 값들 중 가장 작은 값을 하나 뽑아야하기 때문에, 시간복잡도가 O(kn^2) 이 걸려 다른 방법을 찾기로 했다.

 

여기서 "arr[i] = i번째 작은 수"라는 것에 착안하여 배열 대신 priority queue를 사용하기로 했고, 지금까지 저장된 가장 작은 값 answer ( pq.top() )을 가져오고, answer에 각각의 단위 소수들을 곱한 값을 다시 저장하면서 주어진 순서의 숫자를 구하기로 했다.

 

첫 제출코드는 다음과 같다

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
vector<int> prime;
int k,n,t;
int answer = 0;
int before_answer = 0;
const long long MAX = (1<<31);

int main(){

    scanf("%d%d",&k,&n);
    for(int i=0;i<k;i++){
        scanf("%d",&t);
        prime.push_back(-t);
    }
    priority_queue<int> pq;
    
    for(auto p : prime){
        pq.push(p);
    }
    for(int i=0;i<n;i++){
        answer = -pq.top();
        pq.pop();
        if(before_answer == answer){
            --i;
            continue;
        }
        //overflow
        for(auto p : prime){
            long long t = (long long)answer * (long long) p;
            if(t >= MAX)
                pq.push(answer * p);
        }
        printf("%d : %d\n",i+1, answer);
        before_answer = answer;
    }

    printf("%d\n",answer);
    return 0;

}

 

(integer overflow 를 처리하는 부분을 누락해서 틀렸습니다를 받았다. 조심하도록 해야겠다.)

 

 

위 코드는 정답은 받을 수 있으나 중복처리를 하지 않아 메모리가 터질 위험이 있다.

또한, 소수 개수가 많아지거나, n이 커지게 된다면  중복값이 많아져 시간초과를 받을 가능성이 크다. 

실제로 메모리와 실행시간도 다른 정답 코드에 비해 많았다.

 

 

다른 방법을 생각봐야 겠다.