백준 1644번 c++ 풀이

전략:

1. 에라토스테네스의 체를 이용하여 소수를 판정하는 con 함수를 정의 하고, 투 포인터 알고리즘을 이용하여 연속합의 경우의 수를 반환하는 primesum 함수를 정의를 하고 적절히 사용한다.

코드:

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int N;
int Primesum(){
	int si = v.size(), l = 0, r = 0, sum = 0, result=0;
	while(l<=r){
		if(sum==N){
			result++;
		}
		if(sum>=N){
			sum-=v[l];
			l++;
		}
		else if(r>=si){
			break;
		}
		else{
			sum+= v[r];
			r++;
		}
	}
	return result;
}
int con(int num){
	if(num%2==0){
		return false;
	}
	for(int i = 3; i<=sqrt(num); i+=2){
		if(num%i==0){
			return false;
		}
	}
	return true;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);                                                              
	cin>>N;
	if(N>=2){
		v.emplace_back(2);
		
	}
	for(int i= 3;i<=N; ++i){
		if(con(i)){
			v.emplace_back(i);
		}
	}
	cout<<Primesum()<<"\n";
	
}