[BOJ 1644번] 소수의 연속합

이번 문제는 투포인터를 개념을 적용해서 바로 풀 수 있었던 문제였던 것 같습니다.

• 에라토스테네스의 체를 통해서 MAXNUM까지의 소수를 구해주었습니다.
• 입력받은 n까지의 소수 개수 세고, 소수를 배열에 담아주었습니다.
• 투포인터 코드를 적용하여 마지막에 경우의 수를 출력해주었습니다.

 

소스코드

#include <iostream>

#define MAXNUM 4000000
using namespace std;

bool check[MAXNUM];
int arr[MAXNUM];
int main(void) {
	int n;
	for (int i = 2; i <= MAXNUM; i++) {
		if (check[i] == false) {
			for (int j = i + i; j <= MAXNUM; j += i) {
				check[j] = true;
			}
		}
	}

	cin >> n;

	int num=0;
	int idx=0;
	for (int i = 2; i <= n; i++) {
		if (check[i] == false) {
			num++;
			arr[idx++] = i;
		}
	}
	int ans = 0, sum = 0, lo = 0, hi = 0;
	while (1) {
		if (sum >= n) 
			sum -= arr[lo++];
		else if (hi == num) 
			break;
		else 
			sum += arr[hi++];
		if (sum == n) 
			ans++;
		
	}

	cout << ans;


}