BOJ : 1644 소수의 연속합

---

[BOJ 1644(G3)리뷰]

지난 문제에 이어서 푼 투 포인터 문제이다.

이 문제는 N이 최대 400만 이므로 완전탐색을 통해 풀면 시간초과가 나게 된다.

또한 소수를 판별하는 알고리즘 역시 일반적인 방법이 아닌 속도를 개선한 알고리즘을 사용해야 한다.

나는 '에라토스테네스의 체' 알고리즘을 이용하여 N까지의 소수를 선별하여 arr벡터에 담는 작업을 했다.
그 후에는 N까지의 소수가 담긴 arr벡터를 이용하여 두개의 포인터로 부분합을 만족하는 경우를 찾으면 된다.

1과 2에대한 예외처리를 하고나서 정답처리가 나왔다.

/*
	21.01.04
	BOJ : 1644 부분합 (https://www.acmicpc.net/problem/1644)
	투 포인터
*/
#include <bits/stdc++.h>
using namespace std;

bool check[4000001];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	vector <int> arr;
	int n;
	cin >> n;

	if (n == 1) {
		cout << 0;
		return 0;
	}

	if (n == 2) {
		cout << 1;
		return 0;
	}

	int rootSqrt = sqrt(n);
	
	for (int i = 2; i <= rootSqrt; i++) {
		if (check[i]) {
			continue;
		}
		for (int j = i + i; j <= n; j += i) {
			check[j] = true;
		}
	}
	
	for (int i = 2; i <= n; i++) {
		if (!check[i])
			arr.push_back(i);
	}

	int s, e, sum, ans;
	s = e = sum = ans=0;
	int size = arr.size();
	while (e<size) {
		if (sum < n) {
			sum += arr[e++];
		}
		else {
			sum -= arr[s++];
		}

		if (sum == n) ans++;
	}
	
	if (!check[n]) ans++;

	cout << ans;
}