백준 1644 - 소수의 연속합

1. 문제 정리
  - 자연수 n이 주어진다.

  - 연속된 소수의 합 == n 이 되는 경우의 수를 구하여 출력한다.
 
2. 접근
  - 이전에 풀었던 two point Alg.를 활용하여 풀기로 하였다.

  - 에라토스테네스의 체를 이용하여 소수로 이루어진 배열을 만든다.

  - 그 배열을 two point Alg.에 이용한다.
 
3. 풀이

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

int n, len;
int ans = 0;
vector<int> prime;

void findPrime(){
    int a[4000001] = {0, };

	for (int i = 2; i <= n; i++)
		for (int j = 2; i * j <= n; j++)
			a[i * j] = 1;

	for (int i = 2; i <= n; i++)
		if (!a[i]) prime.push_back(i);
}

void twoPoint(){
    int low = 0, high = 0;
    int sum = prime[0];

    while (low <= high && high < len)
    {
        if (sum < n)
            sum += prime[++high];
        else if (sum == n)
        {
            ans++;
            sum += prime[++high];
        }
        else if (sum > n)
        {
            sum -= prime[low++];
        }
    }
}

int main(){
    cin >> n;
    findPrime();
    len = prime.size();
    if(len == 0){
        cout << 0;
        return 0;
    }
    twoPoint();
    cout << ans;
}

  - vector<int> prime : 연속된 소수(오름차순)을 저장할 벡터이다.

  - void findPrime() : 에라토스테네스의 체를 이용해 소수를 구하고, 오름차순으로 prime vector에 push_back 한다.

  - twoPoint() : prime vector를 tow Point Alg.을 이용하여 합의 값이 n과 같을 경우 ans 변수의 값을 1 늘려준다.

  - int main() : 위 함수를 순서대로 진행하되, 주의점있다. 바로 소수 배열이 만들어지지 않았을 때 twoPoint()가 동작하는 것인데, 소수 배열이 만들어지지 않는 경우는 n이 1일 때이다.(소수는 2 이상의 약수가 1과 자기 자신인 수이다.) 즉, n의 값이 1일 때, prime vector에는 값이 없으므로 twoPoint()에서 SegmentFault가 일어날 수 있다.

 해당 문제점을 해결하기 위해, 벡터의 길이가 0일 때, 0을 출력하고 main 함수를 종료하도록 구현하였다.
 
4. 소감

 이전에 풀었던 '2003 - 수들의 합 2' 문제와 유사하였다. 다만 차이는 문제에서 원하는 답이 다르다는 것, 그리고 자연수의 수열이 아닌 소수의 연속된 수열이라는 점이 달랐다. 후자는 에라토스테네스의 체를 이용하여 접목하였고, 전자는 two Point Alg.의 분기 부분에서 실행될 동작을 약간 수정하는 것으로 접목하였다.

 난이도에 비해 two Point Alg.와 에라토스테네스의 체에 대한 이해가 있다면 크게 어렵지 않은 문제라고 생각한다.

 

- two-Point Alg. 참고

https://acver.tistory.com/entry/백준-2003-수들의-합-2