BOJ 1644, 소수의 연속합

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

3 : 3 (한 가지)
41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

내 접근

소수 먼저 다 구하고, 소수만 들고 있는 배열 만든 다음에 투 포인터를 쓰면 될까?
에라토스테네스의 체로 소수 구하면 되겠다.
투 포인터로 탐색할 때 left = right = current = 0으로 시작해서 current가 N보다 작으면 범위를 늘려야하니까 right를 1 증가, N 보다 크면 범위 줄여야하니까 left 1 증가.
하나의 목표 N을 구할 수 있는 소수 배열의 연속 집합 경우의 수가 여러개 있을 수 있고, 그것도 구해야한다니까, 투 포인터에서 current가 N보다 크거나 같으면 left 1 증가하도록 해야겠다.
그리고 current가 N이랑 같을 때마다 카운터 증가시켜서 최종 카운팅 값이 경우의 수가 되겠다.

내 구현

#include <cstring>
#include <iostream>
#include <vector>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)

#define MAX 4000000

bool prime[MAX];
int N;
std::vector<int> A;

void initialPrime() {
  for (int i = 2; i * i <= N; i++) {
    if (prime[i]) {
      for (int j = i * i; j <= N; j += i) {
        prime[j] = false;
      }
    }
  }

  for (int i = 2; i <= N; i++) {
    if (prime[i]) {
      A.push_back(i);
    }
  }

  A.push_back(0);
}

void solve() {
  memset(prime, true, sizeof(prime));

  std::cin >> N;

  initialPrime();

  int l = 0, r = 0, count = 0, current = 0;

  while (r < A.size()) {
    if (current >= N) {
      current -= A[l++];
    }

    if (current < N) {
      current += A[r++];
    }

    if (current == N) {
      count++;
    }
  }

  std::cout << count;
}

int main() {
  IO;
  solve();
  return 0;
}

개선 점

경계 조건을 명확하게 하자

while (r < A.size())로 두고, A.push_back(0)으로 마지막에 원소를 하나 추가해서 r == A.size()일 때도 한 번 더 돌 수 있게 하는건 좋은 생각이 아닌 것 같다.

불변식을 명확하게 하면 current는 A[l] 부터 A[r-1]의 합으로 정의하고, 이는 [l, r)의 반 열린 구간이라고 말할 수 있음.

while (true) {
    if (current >= N) {
        if (current == N) count++;
        current -= A[l++];
    } else {
        if (r == A.size()) break;
        current += A[r++];
    }
}

또 다른 풀이

누적 합(prefix sum) 사용: 원소가 전부 양수가 아닐 때는 끝 점 증가가 구간 합 증가가 아닐 수 있음