BOJ 1644번 소수의 연속합

BOJ : https://www.acmicpc.net/problem/1644

github : https://github.com/junho0956/Algorithm/blob/master/1644/1644/%EC%86%8C%EC%8A%A4.cpp

 

N 이 400만까지 나올 수 있다는 것을 무시하고

11번째 코드를 i*i < 4000001; 으로 풀다가 틀리긴 했지만

어렵지않게 해결할 수 있는 문제였습니다.

투포인트 방식을 통해서 좌우를 +1 씩 해주면서 답을 구해주시면 됩니다.

 

#include <iostream>
#include <vector>
using namespace std;
 
int arr[4000001];
vector<int> v;
 
int main() {
    for (int i = 0; i < 4000001; i++) arr[i] = true;
 
    for (int i = 2; i < 4000001; i++) {
        if (!arr[i]) continue;
        v.push_back(i);
        for (int k = i + i; k < 4000001; k += i) arr[k] = false;
    }
 
    int N, sum = 0, ans = 0, left = 0, right = 0, len = v.size();
    cin >> N;
 
    while (left <= right && left < len && right <= len) {
        if (v[left] > N) break;
        if (sum == N) ans++;
        if (sum >= N) sum -= v[left++];
        else {
            if (right == len - 1) break;
            sum += v[right++];
        }
    }
 
    cout << ans;
    return 0;
}