http://www.acmicpc.net/problem/1644
꿈틀꿈틀 알고리즘,
이론은 쉽지만 구현할때 반복하는 조건이나 값의 인덱스가 헷갈린다 많이많이
연습 많이 해봐야할듯
#include
#include
using namespace std;
int N, a[4000005];
bool era[4000005];
int main(void){
// freopen("input.txt", "r", stdin);
scanf("%d", &N);
fill(era+2, era+N+2, true);
for(int i=2; i*i<=N; i++)
if( era[i] == true )
for(int j=i+i; j<=N; j+=i)
era[j] = false;
int idx=0;
for(int i=1; i<=N; i++)
if( era[i] == true )
a[idx++] = i;
int s=0, t=0, count=0, sum=0;
while( !(s==idx && t==idx)){ //머리와 꼬리 모두 끝까지 갈때까지
if(sum == N){ //원하는 합이 나오면 꼬리부분을 빼줌
count++;
sum -= a[s++];
}
else if(sum < N && t< idx) //찾는 합보다 작으면 머리 더해주고
sum += a[t++];
else if(sum > N && s< idx) //찾는 합보다 크면 꼬리를 빼줌
sum -= a[s++];
else
break;
}
printf("%d\n", count);
return 0;
}
