백준 1644 - 소수의 연속합, C++, 에라토스테네스의 채, 두 포인터

1644번: 소수의 연속합

<첫 제출에 사용한 소스코드>

#include <iostream>
#include <vector>
using namespace std;

int n;
long long arr[4000001];
vector<int> primeNumber;


void FindPrime(){
    arr[0] = -1;
    arr[1] = -1;

    for(long long i = 2; i <= 4000000; i++)
        arr[i] = i;
    
    for(long long i = 2; i <= 4000000; i++){
        if(arr[i] == i){
            for(long long j = i * i; j <= n; j += i){
                if(arr[j] == j)
                    arr[j] = -1;
            }
        }
    }

    for(long long i = 0; i <= 4000000; i++){
        if(arr[i] == i)
            primeNumber.push_back(i);
    }
}


int main(){
    cin >> n;

    FindPrime();

    int left = 0, right = 0, res = 0;
    int sum = primeNumber[0];

    while (left <= right && primeNumber[left] <= n && right < primeNumber.size()){
        if(sum < n){
            right++;
            sum += primeNumber[right];
        }
        else if(sum > n){
            sum -= primeNumber[left];
            left++;
        } 
        else if(sum == n){
            res++;
            right++;
            sum += primeNumber[right];
        }
    }
    
    cout << res << '\n';
}

<시간 / 메모리 개선을 한 소스코드>

#include <iostream>
#include <vector>
using namespace std;

int n;
bool notPrime[4000001];
vector<int> primeNumber;


void FindPrime(){
    for(int i = 2; i * i <= n; i++){
        if(!notPrime[i]){
            for(int j = i * i; j <= n; j += i)
                notPrime[j] = true;
        }
    }

    for(int i = 2; i <= n; i++){
        if(!notPrime[i])
            primeNumber.push_back(i);
    }
}


int main(){
    cin >> n;

    if(n == 1 || n == 0){
        cout << 0 << '\n';
        return 0;
    }

    FindPrime();

    int left = 0, right = 0, res = 0;
    int sum = primeNumber[0];

    while (left <= right && right < primeNumber.size()){
        if(sum < n){
            sum += primeNumber[++right];
        }
        else if(sum > n){
            if(left == right)
                sum += primeNumber[++right];
            else
                sum -= primeNumber[left++];
        } 
        else if(sum == n){
            res++;
            sum += primeNumber[++right];
        }
    }
    
    cout << res << '\n';
    return 0;
}

---

 처음 문제를 풀이할 때는 최대값인 400만까지를 기준으로 잡아서 풀이를 했습니다. 

 

  1. 에라토스 테네스의 채로 소수를 구한 걸 배열에 넣는다

  2. 구한 배열에서 두 포인터 알고리즘을 사용한다.

 

위 2가지 순서를 따르면 되는 문제였으나 시간과 메모리를 너무 많이 잡아먹는 알고리즘이 나왔습니다. 이를 위해서 아래 2가지 개선점을 찾았는데

 

  1. 에라토스 테네스의 채를 계산할 때 400만까지가 아닌 n까지만 함으로서 시간을 줄인다.

  2. long long 배열에 값을 저장하기 보다는 bool배열을 이용해 풀이하자.

 

위 2가지 방법을 적용하니 속도도 4배 빠르고 메모리도 엄청 아끼는 결과를 만들 수 있었습니다. 다만 문제에서 1, 0에 대한 케이스가 필요하다고 해서 위에 따로 예외 처리를 해 줬습니다.