[백준 1644] 소수의 연속합

 

 심플한 투 포인터 문제이다. [1, N] 구간 내에 있는 모든 소수를 구해 배열로 만든다음, 투 포인터를 활용해 제일 작은 소수부터 차례대로 탐색해 나가면 된다. 먼저 소수 배열부터 만드는데, N이 최대 4,000,000까지 될 수 있으므로 O(n)인 방법으로 소수를 판별해서는 안된다(각 판별마다 O(n)만큼 걸리는데 이를 1~n까지 반복해줘야 하기 때문).

 나는 약수를 제곱근까지만 탐색하고, 2의 배수와 3의 배수는 따로 처리해 최적화 하는 방법을 사용했다. 이는 O(n^0.5)에 해당하며, 약수 탐색 간격이 6이기 때문에 실질적으로는 더 빠르다. 물론, 범위가 크기 때문에 에라토스테네스의 체를 사용해도 무방하다.

 

 소수 판별하는 로직을 작성해, [1, N] 구간 내의 소수 배열을 완성했다면 제일 앞부터 탐색을 하면된다. 현재 합 값을 0으로 시작해서, 이 합 값이 N보다 작으면 right 포인터를 증가시키면서 오른쪽 끝의 새 원소를 더해주고, N보다 크다면 left 포인터를 증가시키면서 왼쪽 끝 원소를 빼주면 된다. 합 값이 N과 같으면 결과로 출력할 변수의 값을 1 증가시키고, right나 left 포인터 중 하나를 증가시키는 과정을 실행해서 다음 탐색을 이어가도록 한다.

 포인터 중 하나라도 끝에 다다른다면, 투 포인터 탐색을 종료하고 결과 값을 출력하면 끝이다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> primeNum;

bool isPrime(int n) {
    if(n==2 || n==3) {
        return true;
    } else if(n%2==0 || n%3==0) {
        return false;
    }

    for(int i=5; i*i<=n; i+=6) {
        if(n%i==0 || n%(i+2)==0) {
            return false;
        }
    }

    return true;
}

int main() {
    int n;
    cin >> n;

    for(int i=2; i<=n; i++) {
        if(isPrime(i)) {
            primeNum.push_back(i);
        }
    }

    int left = 0, right = 0;
    int sum = 0, result = 0;
    while(left<primeNum.size() && right<=primeNum.size()) {
        if(sum==n) {
            result++;
            sum += primeNum[right];
            right++;
        } else if(sum<n) {
            sum += primeNum[right];
            right++;
        } else {
            sum -= primeNum[left];
            left++;
        }
    }

    cout << result;
}