백준 1644 소수의 연속합(c++)

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

1644번: 소수의 연속합

이 문제를 해결하기 위해 적용한 것은 에라토스테네스의 체, 투 포인터 알고리즘입니다.

에라토스테네스 체는 2의 배수(2는 제외, 소수이므로)부터 특정 수의 배수까지 걸러주는 알고리즘입니다. 

 

출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

기존 For문을 이용해 푸는 것 보다 훨씬 효율적으로 시간을 절약시킬 수 있게 됩니다. 

 

투 포인터 알고리즘

두 개의 포인터를 이용해 문제를 해결하는 알고리즘입니다. 보통 l(left), r(right)나 s(start), e(end) 같은 식으로 포인터의 이름을 붙인다. 

 

풀이 방법

• 부분합 배열의 합 < 구해야하는 값
• end를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 증가시킵니다.

• 부분합 배열의 합 >= 구해야하는 값
• start를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 감소시킵니다.

시간 복잡도도 O(2N) ~= O(N)이므로 2중 포문을 통해 결과를 구하는 것보다 시간 복잡도적으로 더욱 효율적으로 풀 수 있게 됩니다.

 

<코드>

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> PrimeNumber;
int n;
// 투 포인터 알고리즘
// 2개의 포인터를 사용하여 구간의 길이를 가변적 적으로잡아가며 특정 조건을 만족하는 구간을 찾는다. 모든 연속 구간을 잡는다면 O(N^2)이 될 것이지만 투 포인터 알고리즘을 사용하면 O(N) 의 시간복잡도로 풀 수 있다. 두 포인터 각각 N번 움직이기 때문에 N + N = 2N 번의 연산이 있는 셈이다
vector<int> addPrime(int number)
{
    vector<bool> P(number + 1, true);
    for (int i = 2; i <= sqrt(number); i++)
    {
        if (P[i])
        {
            for (int j = i + i; j <= number; j += i)
            {
                P[j] = false;
            }
        }
    }

    for (int i = 2; i <= number; i++)
    {
        if (P[i])
            PrimeNumber.push_back(i);
    }
    return PrimeNumber;
}

int main()
{

    cin >> n;
    if (n == 1)
    {
        cout << 0 << '\n';
        return 0;
    }
    addPrime(n);
    int left = 0, right = 0, sum = PrimeNumber[0], cnt = 0;

    while (left <= right && right < PrimeNumber.size())
    {
        if (sum < n)
        {
            sum += PrimeNumber[++right];
        }
        else if (sum == n)
        {
            cnt++;
            sum += PrimeNumber[++right];
        }
        else if (sum > n)
        {
            sum -= PrimeNumber[left++];
        }
    }
    cout << cnt << '\n';
}