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

문제링크 : https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
vector<bool>v;
vector<int>p;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    v.resize(N+1);
    for (int i = 2; i*i <= N; i++) //사전에 소수 판별
    {
		if (v[i]) continue;
		for (int j = i*i; j <= N; j+=i) 
        {
			v[j] = 1;
		}
	}

    for(int i=2; i<=N; i++) //소수 저장
    {
        if(!v[i]) p.push_back(i);
    }

    int l=0, r=0, sum = 0, result = 0;
    while (sum >= N || r != p.size())
	{
		if (sum >= N) sum -= p[l++]; //초과
		else sum += p[r++]; //미만
		if (sum == N) result++; //같음
	}
    cout << result;
    return 0;
}

먼저 에라스토테네스의 체 방법으로 N이하의 소수를 모두 찾아주고 이를 벡터에 저장하고 시작한다.

담았던 소수들을 기준으로 투 포인터를 이용해 합을 찾아나간다.

 

합이 N보다 크거나 같다면 맨왼쪽의 값을 제거하고 왼쪽 포인터를 하나 증가시킨다.

합이 N보다 작다면 맨 오른쪽의 값을 추가하고 오른쪽 포인터를 하나 증가시킨다.

이렇게 반복하다가 합이 N과 같은 순간에 결과값을 하나씩 증가시켜주면 된다.

 

종료조건은 합이 N보다 작은데 r이 소수를 담은 p.size()와 같을 때이다.

r이 오른쪽으로 이동하는 포인터인데 이 값이 p.size()와 같다는 것은 맨 오른쪽까지 모두 탐사했다는 뜻이다.

여기서부터는 더 이상 오른쪽으로 포인터를 이동하여 값 추가가 불가능하기 때문에 왼쪽 포인터를 이동하여 기존 값 제거밖에 못하는데, 이미 합이 N보다 작다는 것은 아무리 조정한들 합이 N과 같을 수 없다는 것을 의미한다.

따라서 해당 조건일때는 결과값이 존재할수 없으므로 종료시켜준다.