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

이 문제는 투 포인터를 이용해서 풀었다.

 

자연수 N이 최대 400만이므로, 400만 이하의 소수를 찾으면 된다.

 

연속된 소수의 합으로만 나타내야하므로, 투 포인터를 쓰면 딱 맞다.

만약 acc가 N보다 작다면 right을 증가시켜주고, 크다면 left를 증가시켜 문제를 해결할 수 있다.

400만 이하의 소수의 개수는 약 30만개이므로, 충분히 시간 안에 풀 수 있다.

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

#define MAX 4000000

int N;
bool isPrime[MAX + 1];
vector<int> primes;

void init() {
	for (int i = 0; i <= MAX; i++) {
		isPrime[i] = true;
	}
}

void eratos() {
	for (int i = 2; i * i <= MAX; i++) {
		if (!isPrime[i]) {
			continue;
		}

		for (int j = i * i; j <= MAX; j += i) {
			isPrime[j] = false;
		}
	}

	for (int i = 2; i <= MAX; i++) {
		if (isPrime[i]) {
			primes.push_back(i);
		}
	}
}

void input() {
	cin >> N;
}

int findAnswer() {
	int size = primes.size();
	int left = 0;
	int right = 0;
	int acc = 2;
	int result = 0;
	
	while (right < size && left <= right) {
		if (left == right) {
			if (acc == N) {
				result++;
			}

			right++;
			if (right < size) {
				acc += primes[right];
			}
		} else {
			if (acc <= N) {
				if (acc == N) {
					result++;
				}

				right++;
				if (right < size) {
					acc += primes[right];
				}
			} else {
				acc -= primes[left];
				left++;
			}
		}
	}

	return result;
}

int solve() {
	return findAnswer();
}

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

	init();
	eratos();
	input();
	cout << solve() << '\n';

	return 0;
}