급하게임개발

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

이 문제는 투포인터 문제이다 또한 에라토스테네스의 체로 소수를  걸러내야한다. 이후  투포인터로 연속된 소수의 합을 구하면 된다 

예시로 우리 15라는 숫자를 연속 된 소수로 만들자고 가정하자
15밑의 소수는

이렇게 존재 한다 우리가 연속 된 소수의 합을 만들기 위해서는 Start부분과 End부분이 있으면 된다

star부터 end까지의 합이 우리가 구하려는 숫자보다 작을 때 end의 index를 1증가 시켜주고 아니면 start의 인덱스를 증가시킨다 구하려는 값과 같으면 해당 구간에서는 이미 구해진 것이므로 start의 인덱스 와 end인덱스를 1증가시켜준다

이런느낌으로 구간을 바꿔가면서 계산 해주면 된다

#include <iostream>
#include <vector>
using namespace std;
vector<int> primeNumbers;
vector<int> check;

//n 이하의 정수에 대한 소수를 에라토스테네스의 체로  걸러냄
void getPrimeNumbers(int n) {
	for (int i = 2; i <= n; i++) {
		if (check[i])
			continue;
		else {
			primeNumbers.push_back(i);
			for (int j = i; j <= n; j += i) {
				check[j] = 1;
			}
		}
	}
}
int main() {
	int n,start,end,cnt;
	cin >> n;
	check.resize(n + 1, 0);
	getPrimeNumbers(n);
	start = primeNumbers[0];
	end = primeNumbers[0];
	int startidx = 0;
	int endidx = 0;
	cnt = 0;
	while (startidx <= endidx && endidx<primeNumbers.size()) {
		int sum = 0;
		for (int i = startidx; i <= endidx; i++) {
			sum += primeNumbers[i];
		}
		if (sum == n) {
			cnt += 1;
			startidx += 1;
			endidx += 1;
		}
		else  if (sum < n) {
			endidx += 1;
		}
		else {
			startidx += 1;
		}	
	}
	cout << cnt;
}