백준 - 소수의 연속합(1644)

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

1644번: 소수의 연속합

 

기본기가 중요한 문제였다.

뭔가 기업코테에 출제할만한 문제라고 생각한다.

 

에라토스테네스의 체로 소수의 수열을 구해주었다.

그 후 투포인터로 수열의 합을 구했다.

수열의 합을 구할때는 시간을 더 아끼기 위해 누적합을 이용했다.

q가  오른쪽 포인터 p가 왼쪽포인터로 구간을 나타낼 수가 있으며

q가 올라가면 더해주고 p가올라가면 원래 자리에 있던 수를 빼준다.

 

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	if (n == 1) {
		cout << 0;
		return 0;
	}
	vector<int> prime_data;
	vector<bool> flag_data;
	for (int i = 0; i < n + 1; i++)
		flag_data.push_back(true);
		
	for (int k = 2; k < sqrt(n) + 1; k++) {
		if (flag_data[k]) {
			for (int j = k + k; j <= n; j += k)
				flag_data[j] = false;		
		}	
	}
	
	for (int i = 2; i < flag_data.size(); i++) {
		if (flag_data[i])
			prime_data.push_back(i);
	}

	int p = 0;
	int q = -1;
	int sum_data = 0;
	int prime_size = prime_data.size() - 1;
	int answer = 0;
	while ((p != prime_size) && (q != prime_size)) {
		if (sum_data < n)
		{
			q += 1;
			sum_data += prime_data[q];
		}
		else if (sum_data >=n) {
			if (sum_data == n) 
				answer += 1;
			sum_data -= prime_data[p];
			p += 1;
		}
	}
	if (flag_data[n]) { answer += 1; }
	cout << answer;
}