(C++) 백준 1644 : 소수의 연속합

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

1644번: 소수의 연속합

 이 문제는 연속된 부분합을 구하는 문제와 거의 유사한 문제입니다. 다른점은 어떠한 리스트가 주어지고 그 리스트에서의 부분합을 구하는게 아니라는 점입니다. 이 문제에서는 소수를 직접 구하고, 구한 소수를 이용해야합니다. 따라서 이 문제는 소수를 구하기, 연속된 부분합이 N이 되는 경우의수 구하기로 나눌 수 있습니다. 

 

문제 풀이 

 먼저 필요한 소수를 구해야 하는데 어디까지 구해야 하는지 생각해 보아야 합니다. 연속된 소수의 부분합이 N이 되는 경우의 수를 구해야 하는데 이 말인 즉슨 N까지의 소수를 모두 구해야 한다는 말이됩니다. 즉, 소수를 N보다 작게 구하면 안되고 N보다 크게 구할 필요도 없습니다. 만약 N보다 작은 소수만을 구한다면 구하려는 수 N이 소수일 때 무조건 문제가 생기게 됩니다. 소수 N 하나로 이루어진 부분합이 제외되기 때문입니다. N보다 큰 소수들의 합으로는 당연히 N을 만들지 못하므로 N보다 큰 소수도 구할 필요가 없습니다. 

 소수를 구하는 방식은 여러가지가 있는데 에라토스테네스의 체를 사용하면 N까지의 모든 소수를 쉽게 구할 수 있습니다. 소수의 배수를 통해 소수가 아닌 수들을 모두 지워서 소수를 찾는 방식입니다. 자세한 설명은 링크를 통해 확인할 수 있습니다. 

 

void Eratos(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!isPrime[i]) continue;
		for (int k = i + i; k <= n; k += i)
			isPrime[k] = false;
	}

 에라토스테네스의 체 알고리즘을 이용하여 isPrime에 N까지의 모든 소수가 아닌 수를 false로 만들어 주었습니다. 이후 isPrime이 true인 값들만 배열에 넣어주어서 이용하면 됩니다.

 

 다음은 이 소수들을 이용해 부분합이 N이되는 경우의 수를 구해야합니다. 이 부분은 투포인터를 사용해 풀 수 있습니다. arr가 소수가 들어있는 배열이고 s,e는 각각 배열의 특정 위치를 가리키는 변수이고 sum은 s부터 e까지 값들의 합입니다. 그리고 result가 모든 경우의 수 입니다. 

sum = arr[s];
	while (s < arr.size())
	{
		if (sum > N) sum-=arr[s++];
		else if (sum < N)
		{
			if (++e >= arr.size()) break;
			sum += arr[e];
		}
		else
		{
			result++;
			sum -= arr[s++];
		}
	}

 s와 e는 0부터 시작해서 sum이 N보다 작으면 sum을 더 크게 만들어줘야 하기 때문에 e를 증가시켜서 값을 더해주고, sum이 N보다 크다면 sum을 더 작게 만들어 줘야 하기 때문에 s를 증가시켜 값을 빼줍니다. 만약 sum과 N이 같다면 result를 증가시켜주고 배열 끝까지 이 과정을 반복합니다. 이를 통해 부분합이 N인 모든 경우의 수를 구할 수 있습니다.

 

전체 코드입니다.

#include<iostream>
#include<vector>

bool isPrime[4000001];
std::vector<int> arr;

void Eratos(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!isPrime[i]) continue;
		for (int k = i + i; k <= n; k += i)
			isPrime[k] = false;
	}
}

int main() {
	int N,result=0,s=0,e=0,sum;
	std::cin >> N;
	std::fill(isPrime + 2, isPrime + N + 1, true);
	if (N == 1) {
		std::cout << 0;
		return 0;
	}
	Eratos(N);
	for (int i = 2; i <= N; i++)
		if (isPrime[i])
			arr.push_back(i);
	sum = arr[s];
	while (s < arr.size())
	{
		if (sum > N) sum-=arr[s++];
		else if (sum < N)
		{
			if (++e >= arr.size()) break;
			sum += arr[e];
		}
		else
		{
			result++;
			sum -= arr[s++];
		}
	}
	std::cout << result;
	return 0;
}