Baekjoon 1644 소수의 연속합

Link https://www.acmicpc.net/problem/1644

소스결과 8972 KB / 32 ms

출처 BOJ

언어 C++ 17

분류 에라토스테네스의 체, 투 포인터

 

설명

특정 값을 연속된 소수의 합으로 나타내자

 

소수를 구하는 것도 문제, 어떻게 연속합을 구하는지도 문제

소수는 에라토스테네스의 체로 구하면 상당히 빠른 시간 내에 구해진다.

 

다만 연속합에 대해서 투 포인터 알고리즘을 모른다면 해결이 불가능한 문제가 된다.

prefixSum으로 어찌어찌 비벼볼 수 있겠다는 생각이 들긴 하지만! 최대 범위가 400만이기 때문에 거의 불가능에 가깝다.

따라서 피벗을 이용한 투 포인터 알고리즘을 사용하자.

 

알고리즘

1. 에라토스테네스의 체를 이용하여 소수를 구한다.

2. 투포인터 알고리즘을 이용하여 경우의 수를 찾아낸다.

 2.1 왼쪽과 오른쪽 피벗을 0으로 초기화한다.

 2.2 현재까지의 합이 목표 값보다 작으면 오른쪽 피벗을 +1 하고 해당 위치의 값을 합에 추가한다.

 2.3 현재까지의 합이 목표 값보다 크면 왼쪽 피벗을 +1 하고 해당 위치의 값을 합에서 뺀다.

 2.4 합이 목표값과 일치하면 결과값을 +1 한다.

3. 종료조건은 오른쪽 피벗이 입력 값보다 커지거나 마지막 소수에 다다르면 종료한다.

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 4000000;

bool prime[MAX + 1] = { true, true };

vector<int> primes;

void eratos() {

	for (int i = 2; i <= MAX; i++)
	{
		if (!prime[i])
		{
			primes.push_back(i);

			for (int j = i * 2; j <= MAX; j += i) {
				prime[j] = true;
			}
		}
	}
}

int main()
{
	eratos();

	int n; cin >> n;
	int res = 0;

	int left = 0, right = 0;
	int subSum = 0;

	while (right < primes.size()) {
		if (subSum >= n) subSum -= primes[left++];
		else if (right > n) break;
		else subSum += primes[right++];
		if (subSum == n) res++;
	}

	cout << res;

	return 0;
}