백준 1644번 소수의 연속합

김두현·2023년 1월 21일

목록 보기

75/133

🔒[문제 url]

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

🔑알고리즘

소수가 담긴 배열을 생성하기 위해 에라토스테네체의 체를 적용한다.
이후 Two pointer를 이용해 연속된 소수의 합이 $N$ 과 같아지는 횟수를 출력한다.

에라토스테네체의 체?

$k$ 이하의 소수를 구하고자 한다면, $2 \leq i \leq \sqrt k$ 인 모든 정수 $i$ 에 대하여, 자기 자신을 제외한 $i$ 의 배수를 제거한다.

20미만의 소수를 구한다고 가정하자.
$\sqrt 20$ 은 약 4.47이므로, $2 \leq i \leq 4$ 인 $i$ 에 대해 윗 과정을 진행한다.

$i = 2$
2 , 3, 4 , 5 , 6, 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20

$i = 3$
2 , 3, 4 , 5 , 6, 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20

$i = 4$
2 , 3, 4 , 5 , 6, 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20
최종적으로 남은 2 3 5 7 11 13 17 19가 범위 내의 모든 소수가 된다.

윗 과정을 통해 구한 소수 배열에 Two pointer를 적용해 $N$ 과 비교한다.

연속된 소수의 합이 $N$ 보다 작다면, 오른쪽 포인터를 옮긴다.

연속된 소수의 합이 $N$ 과 같다면, ans++를 해준 후 오른쪽 포인터를 옮긴다.

연속된 소수의 합이 $N$ 보다 크다면, 왼쪽 포인터를 옮긴다.

입력받은 $N$ 이 $1$ 인 경우 예외처리 해주어야함에 유의한다.

🐾부분 코드

void Eratos(int num)
{
    // 에테체
    for(int i = 2; i*i <= num; i++)
        if(!visited[i])
            for(int j = 2; i*j <= num; j++)
            {//자신을 제외한 i의 배수를 제거한다.
                visited[i*j] = true;
            }
}

<에라토스테네체의 체>
위에서 설명한 알고리즘에 따라 소수를 판정한다.

int TP()
{
    int ans = 0;

    int start = 0,end = 0, sum = pN[0];
    while(end < pN.size())
    {
        if(sum <= n)
        {
            if(sum == n) ans++;//합이 N과 같다면
            sum += pN[++end];//합이 N 이하라면 오른쪽 포인터 옮김
        }
        else
        {//합이 N보다 크면
            if(start == end)
            {//두 포인터의 위치가 같다면 둘 다 옮긴다.
                start++; end++;
                sum = pN[start];
            }
            //두 포인터의 위치가 다르면 왼쪽 포인터를 옮긴다
            else sum -= pN[start++];
        }
    }
    return ans;
}

<Two Pointer 함수>

void SOLVE()
{
    if(n == 1) cout << 0, exit(0);

    Eratos(n);

    for(int i = 2; i <= n; i++)
        if(!visited[i])
            pN.push_back(i);

    cout << TP();
}

<전체 알고리즘>
입력된 $N$ 이 $1$ 인 경우 예외처리 해준다.
이외의 경우, 에라토스테네체의 체를 적용해 소수를 판별한 수, 소수의 배열을 만들어 Two pointer를 적용해 답을 구한다.

🪄전체 코드

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

int n;
bool visited[4000001];
vector<int> pN;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
}

void Eratos(int num)
{
    // 에테체
    for(int i = 2; i*i <= num; i++)
    {
        if(!visited[i])
        {
            for(int j = 2; i*j <= num; j++)
            {
                visited[i*j] = true;
            }
        }
    }
}

int TP()
{
    int ans = 0;

    int start = 0,end = 0, sum = pN[0];
    while(end < pN.size())
    {
        if(sum <= n)
        {
            if(sum == n) ans++;//합이 N과 같다면
            sum += pN[++end];//합이 N 이하라면 오른쪽 포인터 옮김
        }
        else
        {//합이 N보다 크면
            if(start == end)
            {//두 포인터의 위치가 같다면 둘 다 옮긴다.
                start++; end++;
                sum = pN[start];
            }
            //두 포인터의 위치가 다르면 왼쪽 포인터를 옮긴다
            else sum -= pN[start++];
        }
    }
    return ans;
}

void SOLVE()
{
    if(n == 1) cout << 0, exit(0);

    Eratos(n);

    for(int i = 2; i <= n; i++)
        if(!visited[i])
            pN.push_back(i);

    cout << TP();
}

int main()
{
    INPUT();
    SOLVE();
}