백준 1644번 - 소수의 연속합

백준 1644번 - 소수의 연속합

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

문제

• 2 이상의 자연수가 주어졌을 때,

• 이 자연수를 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 경우의 수

• 예를 들어,

  • 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)

입력

• 자연수 N (1 ≤ N ≤ 4,000,000) 

출력

• 경우의 수

접근

• 에라토스테네스의 체를 활용하여 n 까지의 소수를 미리 구함

• 투 포인터를 활용하여 포인터 2개 사이의 구간합을 구해가며 n가 같음을 확인

  • 구간합이 n보다 작으면 우측의 포인터를 증가

  • 구간합이 n보다 크거나 같으면 좌측의 포인터를 증가

  • 우측의 포인터가 끝에 도달하면 종료

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
​
int n;
vector<int> primes;
vector<bool> check;
​
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    //에라토스테네스의 체
    check.resize(n + 1, true);
    for (int i = 2; i*i <= n; i++)
    {
        if (!check[i]) continue;
        for (int j = i * i; j <= n; j += i)
        {
            check[j] = false;
        }
    }
​
    for (int i = 2; i <= n; i++)
    {
        if (check[i]) primes.push_back(i);
    }
​
    //투포인터를 이용
    //1. lo와 hi 사이의 구간합을 구한다.
    //2. 구간합이 n보다 크거나 같으면 가장 왼쪽의 수를 뺀다.
    //3. 구간합이 n보다 작으면 가장 오른쪽의 수를 더한다.
    int result = 0, sum = 0, lo = 0, hi = 0;
    while (1) {
        if (sum >= n) {
            sum -= primes[lo++];
        } else if (hi == primes.size()) {
            break;
        } else {
            sum += primes[hi++];
        }
​
        if (sum == n) result++;
    }
​
    cout << result;
​
    return 0;
}