[백준] 1644번 소수의 연속합

문제 링크: https://www.acmicpc.net/problem/1644

문제 및 입출력

문제 접근

연속합이므로, 두 포인터로 구할 수 있는 문제이다.
2부터 입력받은 수까지의 소수들을 에라토스테네스의 체를 사용하여 구한다.
해당 소수들을 vector에 넣는다.
구간의 앞 뒤를 가르키는 두 개의 포인터를 만든다.
두 포인터가 처음에는 맨앞을 가르킨다.
구간의 합이 target보다 작다면, end pointer를 +1 해주고, sum에 더한다.
구간의 합이 target보다 크거나 같다면, sum에서 start가 가르키는 수를 빼주고, start를 +1 해준다. 만약 sum과 target이 같다면 result를 +1해준다.
소수가 아예 없을 경우의 수를 생각하지 못해, outofbounds 런타임 에러가 계속 나타났다.

코드 구현(c++)

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
bool num[4000001];
vector <int> v;// 소수 넣는 vector
int target;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> target;
    memset(num, false, sizeof(num));
    for(int i = 2 ; i <= target ; i++){
        for(int j = i*2 ; j <= target ; j = j+i){
            num[j] = true;
        }
    }
    for(int i = 2 ; i <= target ; i++){
        if(!num[i]) v.push_back(i);
    }
    int start = 0;
    int end = 0;
    int result = 0;
    int maxSize = v.size();
    if(maxSize != 0){
        int sum = v[start];
        while(end <= maxSize && start <= end){
            if(sum >= target){
                if(sum == target) result++;
                sum -= v[start];
                start++;
            }
            else{
                end++;
                //if(end > maxSize) break;
                sum += v[end];

            }
        }
    }
    cout << result << "\n";
}