꿈틀꿈틀

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; }