[C++/백준] 1644번: 소수의 연속합*

문제 링크

1644번: 소수의 연속합

 

풀이

투포인터랑 누적합 문제. 투포인터는 항상 헷갈리는게 각 포인터를 양 옆에 설정하느냐 아니냐 생각이 드는데 .. 그냥 같은 방향에서 시작하는 게 맞는 것 같다.

1. 에라토스테네스의 체를 이용해서 n까지의 소수들을 구해준다.
   1. 여기서 팁은 i가 굳이 n까지 갈 필요 없이 제곱근까지만 구해주면 된다는 것
2. 소수들의 누적합을 구해 sosuSum에 넣어준다.
3. 투포인터를 이용해 연속합이 n인 구간의 경우의 수를 구해주는데, 여기서 투포인터를 사용한다.
   1. 각 포인터는 0과 1 인덱스로 설정한 뒤, en에서 st를 빼주면 구간의 합이 나온다.
   2. 이 합이 n과 같을 경우는 answer++
   3. 2번과 상관없이 포인터를 재설정해줘야 하는데, n보다 큰 쪽에 넣든 작은 쪽에 넣든 상관없이 같을 때도 포인터 재설정을 해줘야한는게 포인트
   4. 구한 합이 n보다 크면 구간을 줄여줘야하기 때문에 st++, 작으면 구간을 늘려야하기 때문에 en++하면 된다.
   5. en이 size()와 같다면 마지막에 도달한 것이기 때문에 (여기서 size()-1로 해주면 위에서 이미 포인터를 늘린 상태라 마지막 구간이 체크가 안된다. 예시였던 41을 넣어보면 확인가능) break해준다.

 

코드

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

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n+1);
    vector<int> sosuSum;

    arr[1] = 1;
    for (int i = 2; i*i <= n; i++)
    {
        if (arr[i] == 0)
        {
            for (int j = 2; i * j <= n; j++)
            {
                arr[i * j] = 1;
            }
        }
    }

    int sum = 0;
    sosuSum.push_back(0);
    for (int i = 1; i <= n; i++)
    {
        if (arr[i] == 0)
        {
            sum += i;
            sosuSum.push_back(sum);
        }
    }

    if (n == 1)
    {
        cout << 0;
        return 0;
    }

    int answer = 0;
    int st = 0;
    int en = 1;
    while (1)
    {
        int tmp = sosuSum[en] - sosuSum[st];
        if (tmp == n) answer++;
        if (tmp <= n) en++;
        if (tmp > n) st++;
        if (en == sosuSum.size()) break;
    }

    cout << answer;
}