소수의 연속합

코드

[ 나의 풀이 ]

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <deque>
#include <map>
#include <cmath>
#include <numeric>
using namespace std;
int N;
bool arr[4000001];
vector<int> n;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fill(arr, arr+4000001, true);
    arr[1] = false;
    cin >> N;
    for(int i=2;i<=N;i++)
    {
        if(!arr[i]) continue;
        for(int j=2;i*j<=N;j++)
            arr[i*j] = false;
    }
    int cnt=0;
    for(int i=2;i<=N;i++)
        if(arr[i]) n.push_back(i);
    int sum = 0;
    int ans = 0;
    int st=0,en=0;
    while(true)
    {
        if(sum < N){
            if(en < n.size())
                sum += n[en++];
            else if(st < n.size()){
                sum -= n[st++];
            }
        }
        else if(sum > N){
            sum -= n[st++];
        }
        else if(sum == N)
            {
                ans++;
                sum -= n[st++];
            }
        if(st == n.size() and en == n.size()) break;
    }
    cout << ans;
    return 0;
}

• 느낀 점
  • 2개의 변수로 이동해가면서 합을 구하는 것은 알았으나, 두 포인터의 예외상황 처리가 난감했음
    --> 이것을 깔끔하게 정리한게 투포인터 알고리즘 이라는 것이 있었음

---

[ 투포인터 알고리즘 ]

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <deque>
#include <map>
#include <cmath>
#include <numeric>
using namespace std;
int N;
bool arr[4000001];
vector<int> n;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fill(arr, arr+4000001, true);
    arr[1] = false;
    cin >> N;
    for(int i=2;i<=N;i++)
    {
        if(!arr[i]) continue;
        for(int j=2;i*j<=N;j++)
            arr[i*j] = false;
    }
    int cnt=0;
    for(int i=2;i<=N;i++)
        if(arr[i]) n.push_back(i);
    /* 투포인터 알고리즘 - O(N) */
    int sum = 0;
    int ans = 0;
    int st=0,en=0;
    while(true)
    {
        // 마지막 소수가 자기 자신이여도 뒤 수를 빼야함
        if(sum >= N)
            sum -= n[st++];
        else if(en == n.size())
            break;
        else
            sum += n[en++];
        if(sum == N) ans++;
    }
    cout << ans;
    return 0;
}

• 로직
  • 2개의 포인터를 움직여가며 부분합을 구하는 것
  • 사실 기존 풀이와 같으나, 두개의 포인터 예외처리를 깔끔하게 해결함
  • 이렇게 2개의 포인터로 하는 알고리즘을 투포인터 알고리즘 이라고 한단다