[BOJ/C++] 1644: 소수의 연속합

🏅 Gold 3

✏️ 1차 솔루션

⭐️ 소수 판별을 위해 에라토스테네스의 체 사용

1. 에라토스테네스의 체로 n 보다 작은 수 소수 판별
2. n 보다 작은 소수는 각 소수까지의 누적합을 배열에 저장
3. n 보다 작은 소수의 누적합이 n 보다 크거나 같은 경우, 누적합 형성 가능하다고 판단
   ➡️ n 보다 소수의 누적합이 큰 경우, 누적합 - n 의 값이 소수 누적합 중에 존재하면 누적합 형성 가능하다고 판단
   ➡️ 소수 누적합 중에 존재하는지 확인은 find 함수로 하기

🚨 1차 trouble

누적합을 저장하는 과정과 부분합을 저장해서 사용할 때 find 를 사용해서 시간초과 뜨는 것 같지만 이 방법밖에 떠오르지 않았음

✏️ 최종 솔루션

⭐️ 소수 판별을 위한 에라토스테네스의 체와 투포인터 사용

1. 에라토스테네스의 체로 n 보다 작은 수에 대한 소수 판별
2. n 보다 작은 소수는 벡터에 따로 저장
3. 투포인터 사용
   1) start, end 는 0 부터 시작해서 start, end 포인터 위치 바꿔가면서 누적합 판단 ➡️ end 포인터가 소수 벡터의 끝에 도달할 때까지
   2) 누적합이 n 보다 작을 경우, end 포인터를 늘려줘서 누적합의 범위를 늘려서 누적합에 숫자를 더 추가
   3) 누적합이 n 보다 크거나 같은 경우, start 포인터를 늘려줘서 누적합의 범위를 줄여서 누적합에 숫자를 제외시킴
   4) 누적합이 n 일 경우, count++

📌 self feedback

투포인터를 사용해서 누적합을 저장할 저장공간도 save 하고 반복적인 for 문 사용도 방지함으로서 시간 save

✏️ 최종 code

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,end=0,start=0,ans=0,sum=0;
    cin >> n;
    
    if(n==1) {
        cout <<0;
        return 0;
    }
    vector<int> prime;
    
    vector<int> v(n+1,0);
    for(int i=2;i*i<=n;i++) {
        if(v[i]==0) {
            for(int j=i*i;j<=n;j+=i) {
                v[j]=1;
            }
        }
    }
    
    for(int i=2;i<=n;i++) {
        if(v[i]==0) prime.push_back(i);
    }
    
    while(end<=prime.size()) {
        if(sum<n) {
            sum+=prime[end];
            end++;
        }
        else {
            sum-= prime[start];
            start++;
        }
        
        if(sum==n) ans++;
    }
    
    cout << ans;
    
}