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

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

1644번: 소수의 연속합

소수 판별 알고리즘 + 투포인터 알고리즘의 조합이다.

우선, 에라토스테네스의 체를 이용하여 소수를 걸러준다. N의 범위가 4백만이므로 그냥 이중 for문을 사용하면 TLE다.

(소수를 거른다는 것은, 소수끼리만 따로 모아준다는 것을 뜻한다. 그렇게 된다면 자연스레 소수들은 연속되게 된다.)

 

거른 소수를 따로 저장해준 뒤, 이를 이용해 투포인터 알고리즘을 작동시킬 것이다.

 

필요한 변수들을 선언 해준 뒤,  left와 right 사이의 구간합을 구해준다.

이때 구간합이 n보다 작으면 right가 가리키는 소수를 더해준다.

만약 구간합이 n보다 크거나 같으면 left가 가리키는 소수를 빼준다.

 

right가 배열의 끝까지 갔다면 종료시켜주자.

투포인터 알고리즘은 직접 그려보면서 예제를 하나 풀어보면 바로 이해가 되므로 글보다는 그림으로 이해하자!

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

vector<bool> v;
vector<int> prime;

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

    int n;
    cin >> n;
    v.resize(n + 1, true);
    // 에라토스테네스의 체
    for(int i=2; i*i<=n ;i++){
        if(!v[i]) continue;
        for(int j=i*i; j<=n;j+=i){
            v[j]=false;
        }
    }
    // 체를 거른 것들을 저장
    for(int i=2; i<=n; i++){
        if(v[i]) prime.push_back(i);
    }

    int left = 0, right = 0;// 투포인터
    int ans = 0; // 경우의 수
    int sum = 0;
    while (true) {
        if (sum >= n) {
            sum -= prime[left++];
        } else if (right == prime.size()) {
            break;
        } else {
            sum += prime[right++];
        }
        if (sum == n) ans++;
    }
    cout << ans;
    return 0;
}