[백준 C++] 1644 소수의 연속합 - 에라토스테네스의체

1644번: 소수의 연속합

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

bool Prime[4000001];
vector<int> Sequence;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N;
	cin >> N;

	for (int i = 2; i <= N; ++i)
	{
		Prime[i] = true;
	}

	for (int i = 2; i <= N / 2; ++i)
	{
		if (!Prime[i])
		{
			continue;
		}

		for (int j = 2; i * j <= N; ++j)
		{
			Prime[i * j] = false;
		}
	}

	Sequence.reserve(N);
	for (int i = 2; i <= N; ++i)
	{
		if (Prime[i])
		{
			Sequence.emplace_back(i);
		}
	}

	int Cnt = 0;
	int Size = Sequence.size();

	int S = 0;
	int E = 0;
	while (S < Size && E < Size)
	{
		int Sum = 0;
		for (int i = S; i <= E; ++i)
		{
			Sum += Sequence[i];
		}

		if (Sum == N)
		{
			++Cnt;
			++S;
			++E;
		}
		else if (Sum > N)
		{
			++S;
		}
		else
		{
			++E;
		}
	}

	cout << Cnt;
}

---

 

에라토스테네스의 체 & 투 포인터 알고리즘 문제입니다.

풀이과정은 다음과 같습니다.

 

1. 에라토스테네스의 체 기법을 이용해서 1부터 N까지 소수 판별

1-a. bool값을 저장할 1차원 배열 생성
1-b. 2부터 1씩 증가하면서 아직 지워지지 않은 숫자를 선택하고, 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 모두 지운다. - 이때 선택한 숫자는 지우지 않는다.
1-c. 배열의 끝까지 1-b를 반복

2. 벡터 컨테이너에 1부터 N까지 중 소수만 저장

3. 부분 수열의 시작 인덱스와 끝 인덱스를 가리키는 두 개의 변수를 이용해서 연속합 개수 카운팅