문제

링크

접근

1. N보다 작거나 같은 소수를 모두 구한다.
   에라토스테네스의 체 이용
2. 구간합
   투포인터.

구현

1. 에라토스테네스의 체
   그림으로 그리면 알지만 코드로 자면 항상 헷갈린다. 숙지가 필요하다. 여러 방법이 있는데 나의 경우에는 그림으로 그리는 것처럼 하는 게 제일 기억에 잘 남는 것 같다. check 배열을 만들어서 true, false 표기를 할 수 있도록 한다. 그리고 지울 숫자 i를 n의 제곱근 + 1까지 돌리면서 i의 배수를 전부 지워준다.
2. 투포인터
   투포인터에 적응한 것 같다. while문 계속 돌리면서 조건에 따라 l, r을 증가시킨다. 종료 조건에 약간 신경쓸 필요가 있다.

시행착오

1. 입력 1에 대한 출력은 0이어야 한다. 이 때, 1보다 작거나 같은 소수는 존재하지 않기 때문에 vector size = 0이라서 터진다. 예외처리 해줌.

2. 에라토스테네스의 체 범위. sqrt(n) + 1 까지이다. 헷갈릴 때에는 일단 범위 등을 넓게 잡고 고쳐볼 것.

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int check[4000001] = { 0, };
vector<int> primes;
int N;

void primenumbers(int n) {
	// check배열 초기화
	// 1 = not prime number.
	check[0] = 1;
	check[1] = 1;

	for (int i = 2; i < sqrt(n) + 1; i++) {
		if (check[i] == 0) {
			for (int j = i + i; j <= n; j+=i) {
				check[j] = 1;
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		if (!check[i]) 
			primes.push_back(i);
	}

}

int main() {

	cin >> N;

	if (N == 1) {
		cout << "0";
		exit(0);
	}

	// 소수를 일단 구한다
	primenumbers(N);

	/*
	for (int i = 0; i < primes.size(); i++) {
		cout << primes[i] << " ";
	}
	cout << "\n";*/

	
	int l = 0, r = 0;
	int sum = 0;
	int cnt = 0; // answer
	// 투포인터
	while (1) {
		if (l == primes.size() - 1 && r == primes.size()) {
			if (sum == N) cnt++;
			break;
		}

		if (sum == N) {
			cnt++;
			sum -= primes[l];
			l++; // 다음꺼도 구해야지
		}
		else if (sum < N) {
			sum += primes[r];
			r++; // 더 크게 
		}
		else {
			sum -= primes[l];
			l++;
		}
	}

	cout << cnt << "\n";

	return 0;
}