[ 백준 ] 1644번 : 소수의 연속합 - (C/C++/CPP)

•  문제

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

1644번: 소수의 연속합

---

• 풀이법 ( 알고리즘 )

소수는 늘 그렇듯 에라토스테네스의 체를 활용해 구한 후

소수들을 모두 vector array에 넣고 부분합을 계산해 답을 도출하면 된다.

부분합을 구할 때

1. 현재 부분합이 n보다 크면 현재 start가 가리키는 수를 빼고 start 증가
2. 현재 부분합이 n보다 작다면 현재 end가 가르키는 수를 더하고 end 1 증가
3. 현재 부분합이 n과 같다면 경우의 수 ( 답 ) 1 증가

총 3번을 확인하여 각각에 맞는 연산을 해준다.

 

투포인터 알고리즘을 활용하지 않고 이중 for문으로도 답이 나올 수 있을 거 같다.

---

• 풀이 - C++

#include <iostream>
#include <vector>
#include <algorithm>
#include<cmath>
#define MAX 4000000

using namespace std;


int n,ans; // n : 자연수 n
vector <bool> isPrime;
vector <int> prime;

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

	//input
	cin >> n;
	isPrime.resize(n + 1, true);

	//solve

	for (int i = 2; i * i <= n; i++) //소수 구하기 - 에라토스테네스의 체
	{
		for (int j = i * 2; j <= n; j += i)
			isPrime[j] = false;
	}

	for (int i = 2; i <= n; i++) // 소수들을 벡터에 담음 -> 계산 편리
	{
		if (isPrime[i])prime.push_back(i);
	}
	
	//start와 end 사이의 구간합 구하기
	//1 .구간 합이 n보다 크면 현재 start위치에 있는 수를 뺀다.
	//2 .구간 합이 n보다 작으면 현재 end위치에 있는 수를 더한다.
 	//3 .구간 합이 n과 같으면 and 1 증가
    
	int start = 0, end = 0, sum = 0;
	while (1)
	{
		if (sum > n) sum -= prime[start++]; //1번
		else if (end == prime.size()) break; //기저사례 : 현재 가르키는 end가 범위 내의 마지막 소수라면
		else sum += prime[end++]; //2번
		 
		if (sum == n) ans++; //3번
	}

	//output
	cout << ans;
	return 0;
}