(C++) - 백준(BOJ) 1644번 : 소수의 연속합

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

1644번: 소수의 연속합

two pointer로 푼 문제였습니다.

 

 

풀이방법

 1. 400만까지의 소수를 구해 vector 자료형의 변수 prime에 저장합니다. 약 28만개 정도 됩니다.

 

 2. two pointer를 시행합니다.

 

    변수 l과 r을 pivot으로 하여 다음조건에 따라 누적합을 저장할 변수 sum에 적절히 더해가거나 빼면서 수행합니다.

 

    2-1. 가장 처음 소수인 2부터 시작해서 누적합이 n을 초과한다면 l값을 빼주고 구간을 한칸 오른쪽으로 옮겨줍니다.

 

    2-2. 만약 연속구간의 합이 n과 같다면 ans를 더해줍니다. 가장 처음 소수인 2부터 시작해서 누적합이 n이하라면 r을 증가시켜주고 더해줍니다. 

 

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, isPrime[4000001];
vector <ll> prime;

void makePrime(){
    for(int i = 2; i*i <= 4000000; i++){
        if(!isPrime[i]){
            for(int j = i + i; j <= 4000000; j+=i) isPrime[j] = 1;
        }
    }
}

ll twoPointer(){
    ll ans = 0, sum = 0, l = 0, r = 0;
    if(prime.size()) sum = prime[0];
    while(l <= r && r < prime.size()){
        if(sum > n) sum -= prime[l++];
        else {
            if(sum == n) ans++;
            sum += prime[++r];
        }
    }
    return ans;
}

int main(){
    cin >> n;
    makePrime();
    for(int i = 2; i<=4000000; i++) if(!isPrime[i]) prime.push_back(i);
    cout << twoPointer();
}