[투 포인터] BOJ 1644번 소수의 연속합

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

1644번: 소수의 연속합

- 문제 파악

주어진 자연수 N을 소수의 연속합으로 나타낼 수 있다. 이때 나타낼 수 있는 경우의 수를 출력하라. 경우의 수가 없다면 0을 출력하라.

 

- 정답

투 포인터를 이용하여 

N보다 큰 연속합일 때 종료 포인터를 멈추고 시작 포인터를 증가 시킨다. 이전 시작 포인터 값을 연속합에서 빼고 다시 종료 포인터를 N보타 큰 연속합일 때 멈추는 것을 반복한다.

 

위 작업을 반복하여 연속합이 N이 되는 경우의 수를 출력한다.

 

#include "bits/stdc++.h"

using namespace std;

int arr[4000001];

int main()
{
	int n;
	cin >> n;

	vector<int> vec;

	for (int i = 2; i <= n; i++)
	{
		if (arr[i]) continue;

		vec.push_back(i);

		for (int j = 2; i*j <= n; j++)
			arr[i * j] = 1;
		
	}

	int nCnt = 0;
	int ed = 0;
	long long lsum = 0;
	int size = vec.size();

	for (int i = 0; i < size; i++)
	{
		while (ed < size && lsum < n)
		{
			lsum += vec[ed];
			ed++;
		}

		if(lsum == n)
			nCnt++;

		lsum -= vec[i];

	}

	cout << nCnt;

}