[BOJ] 1644번 | 소수의 연속합 (C++)

🔗문제 보러가기

1644번: 소수의 연속합

 

👨‍💻풀이 과정

 

1. 2부터 N까지 소수를 구하는 "에라토스테네스의 체" 알고리즘
2. 1번에서 구한 소수들의 누적합을 저장해 둔 배열
3. 투 포인터를 사용하여 부분 구간을 이동해가며, N이 나오는 구간의 개수를 카운트

 

위 순서대로 저는 문제를 풀었습니다. 투 포인터와 관련된 소스 코드는 많이 작성해보지 않아서 그런지, 짜는 데에 조금 시간이 걸리네요.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>

using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

int main()
{
    FAST_IO
    int N;
    cin >> N;

    // 1. N까지의 모든 소수 구하기 (에라토스테네스의 체)
    vector<bool> isPrimeNumbers(N + 1, true);
    isPrimeNumbers[0] = isPrimeNumbers[1] = false;

    for (int i = 2; i * i <= N; i++)
    {
        if (isPrimeNumbers[i])
        {
            for (int k = i * i; k <= N; k += i)
                isPrimeNumbers[k] = false;
        }
    }

    // 2. 소수로 이루어진 누적합 배열 만들기
    vector<int> accumulatedPrimeNumbers { 0 };
    for (int i = 2; i <= N; i++)
        if (isPrimeNumbers[i])
            accumulatedPrimeNumbers.push_back(accumulatedPrimeNumbers.back() + i);

    // 3. 투 포인터를 통해, 조건에 부합하는 수의 경우의 수 찾기
    int left = 0, right = 1, end = accumulatedPrimeNumbers.size() - 1, answer = 0;
    while (left < end)
    {
        while (right < end and accumulatedPrimeNumbers[right] - accumulatedPrimeNumbers[left] < N)
            right++;

        while (left < right and accumulatedPrimeNumbers[right] - accumulatedPrimeNumbers[left] >= N)
        {
            if (accumulatedPrimeNumbers[right] - accumulatedPrimeNumbers[left] == N)
                answer++;
            left++;
        }

        // right를 끝까지 다 보냈는데 연속합이 N보다 작은 경우, 루프를 끝내주기 위해 left++
        if (right == end)
            left++;
    }

    cout << answer;
    return 0;
}