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

---

- 문제

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

1644번: 소수의 연속합

---

- 문제 분석 및 풀이

연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하기 위해서 일단 풀이 과정을 2가지로 나누었다. 

1. 소수 배열을 구하기
2. 연속된 소수의 합이 N인 경우의 수를 구하기

1) 일단 소수 배열을 구하는 것은 흔히들 사용하는 에라토스테네스의 체를 사용하였다. 

https://blog.naver.com/ndb796/221233595886

22. 에라토스테네스의 체

2) 연속된 소수의 합이 N이 되는 모든 경우를 구하기 위해 누적합배열을 떠올렸고, 이를 표현하기 위한 2가지 선택지 중 고민하였다.

 

- sumPN[i] : 1번째 소수 ~ i번째 소수까지의 합

- sumPN[i][j] : i번째 소수 ~ j번째 소수까지의 합

 

문제의 조건 N의 최대값은 4,000,000이었고, 디버깅을 통해 1~4,000,000사이 소수의 개수는 대략 28만개인것을 확인하였다. 

만약 나이브하게 2차원배열을 순회하는 방법은 쉽지만, 시간초과가 난다.

 

때문에 투포인터 기법을 활용하여 1차원 배열을 O(N)의 시간복잡도로 순회하는 방법을 구현하였다.

2개의 누적합을 빼면, 구간연속합이 되고 이를 통해 해당 값이 N인지 확인하였다.

 

만약 구간합이 N보다 작으면 오른쪽 포인터를 옮겨 구간합을 크게하고, 구간합이 N보다 크면 왼쪽 포인터를 옮겨 구간합을 작게하면서 경우의 수를 확인하였다.

---

- 코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

bool isPrime[4000001];
vector<int> PN;			// 소수배열
vector<ll> sumPN;		// 누적합 배열

void get_init_condi(int n) {
	// 에라토스테네스의 체
	for (int i = 2; i <= n; i++) {
		isPrime[i] = true;
	}
	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {
			for (int j = 2 * i; j <= n; j += i) {
				isPrime[j] = false;
			}
		}
	}
	// 소수 배열 초기화
	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {
			PN.push_back(i);
		}
	}
	// 연속합 배열 초기화
	ll sum = 0;
	sumPN.push_back(0);	// 0을 추가해야 자기 자신도 확인 가능
	for (int i = 0; i < (int)PN.size(); i++) {
		sum += PN[i];
		sumPN.push_back(sum);
	}
}

int solve(int n) {
	// 투 포인터
	int cnt = 0;
	int l = 0;
	int r = 0;
	int size = (int)sumPN.size();

	while (l < size && r < size) {
		ll sum = sumPN[r] - sumPN[l]; // 구간합

		if (sum == n) {
			cnt++;
			l++; r++;
		}
		else if (sum < n) {
			r++;
		}
		else {
			l++;
		}
	}
	return cnt;
}

int main() {
	fastio;

	int n; cin >> n;
	get_init_condi(n);		// 초기조건 설정
	cout << solve(n);		// 결과 출력

	return 0;
}