[PS] 백준 1644번 소수의 연속합

이번에는 백준 1644번 소수의 연속합 문제를 풀어보았습니다.

문제를 처음 봤을 때 먼저 N 이하의 모든 소수를 구해야 한다고 생각했습니다.

이후 연속된 소수들의 합을 구해야 했기 때문에 에라토스테네스의 체로 소수를 구한 뒤, 투 포인터를 이용하여 연속 구간의 합을 관리하도록 구현하였습니다.

---

문제 설명

자연수 N이 주어집니다.

N을 연속된 소수들의 합으로 나타낼 수 있는 경우의 수를 구하는 문제입니다.

같은 소수를 여러 번 사용할 수는 없으며, 반드시 연속된 소수여야 합니다.

---

풀이 아이디어

먼저 에라토스테네스의 체를 이용하여 N 이하의 모든 소수를 구하였습니다.

이후 소수 배열에서 투 포인터를 이용하여 현재 연속 구간의 합을 관리하였습니다.

• 현재 합이 N보다 작으면 오른쪽 포인터를 이동하며 소수를 추가합니다.
• 현재 합이 N보다 크거나 같으면 왼쪽 포인터를 이동하며 가장 앞의 소수를 제거합니다.
• 현재 합이 N과 같다면 경우의 수를 증가시켰습니다.

모든 소수를 한 번씩만 추가하고 제거하므로 효율적으로 해결할 수 있었습니다.

---

코드

#include <bits/stdc++.h>
using namespace std;

bool a[4000001];
int arr[200001];
int p=0;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    for (int i=2; i<=n; i++) {
        if (a[i]) continue;

        for (int j=2*i; j<=n; j+=i) {
            a[j] = true;
        }
    }

    for (int i=2; i<=n; i++) {
        if (!a[i])
            arr[p++] = i;
    }

    int ret = 0;
    int sum = 0;
    int st = 0;
    int ed = 0;

    while(true) {

        if (sum >= n) {
            if (sum == n)
                ret++;

            sum -= arr[st++];
        }
        else {
            if (ed == p)
                break;

            sum += arr[ed++];
        }
    }

    cout << ret << '\n';

    return 0;
}

---

풀이 흐름

1. 에라토스테네스의 체를 이용하여 N 이하의 소수를 구합니다.
2. 소수만 배열에 저장합니다.
3. 투 포인터를 이용하여 연속 구간의 합을 관리합니다.
4. 현재 합이 N보다 작으면 오른쪽 포인터를 이동합니다.
5. 현재 합이 N보다 크거나 같으면 왼쪽 포인터를 이동합니다.
6. 합이 N인 경우 정답을 증가시킵니다.
7. 모든 구간을 확인한 뒤 결과를 출력합니다.

---

구현 포인트

1. 에라토스테네스의 체

먼저 N 이하의 모든 소수를 구하였습니다.

for (int i=2; i<=n; i++) {
    if (a[i]) continue;

    for (int j=2*i; j<=n; j+=i) {
        a[j] = true;
    }
}

이후 소수만 따로 배열에 저장하였습니다.

for (int i=2; i<=n; i++) {
    if (!a[i])
        arr[p++] = i;
}

---

2. 투 포인터

현재 연속 구간은

• st : 시작 위치
• ed : 끝 위치

로 관리하였습니다.

int st = 0;
int ed = 0;

현재 구간의 합은 sum으로 관리하였습니다.

---

3. 합이 작은 경우

현재 합이 N보다 작다면 더 큰 소수를 추가해야 합니다.

if (ed == p)
    break;

sum += arr[ed++];

오른쪽 포인터를 이동하며 새로운 소수를 추가하였습니다.

---

4. 합이 크거나 같은 경우

현재 합이 N보다 크거나 같다면 가장 앞의 소수를 제거하였습니다.

if (sum == n)
    ret++;

sum -= arr[st++];

합이 N과 같으면 경우의 수를 증가시킨 뒤 왼쪽 포인터를 이동하였습니다.

---

5. 시간복잡도

에라토스테네스의 체로 소수를 구한 뒤,

투 포인터에서는 각 소수를 최대 한 번 추가하고 한 번 제거합니다.

따라서 전체 시간복잡도는

O(N log log N + 소수 개수)

으로 충분히 제한 안에서 해결할 수 있었습니다.