BOJ 부분합(1806) 과 마찬가지로 투 포인터 문제인데 이번엔 종만북 풀이가 아닌 라이님의 풀이를 참고하였다.
연속부분수열의 합은 최대 이므로 수열의 원소가 될 소수는 최대 임을 알 수 있다. 소수는 자연수이므로 임의의 연속부분수열의 합이 이 되게 하는 경우의 수는 투 포인터 알고리즘을 이용해서 해결이 가능하다. 소수는 에라토스테네스의 체 알고리즘을 사용해서 에 이하의 소수를 모두 구한다.
종만북 풀이에서는 후보 구간을 정의하고 후보 구간들을 관찰함을 통해 가 증가할 때 이 감소하는 경우는 없음을 발견하고 이를 증명했었다.
이 풀이는 구간의 합이 보다 작으면 을 전진시켜서 구간의 합을 늘리고, 보다 크면 를 전진시켜서 합을 줄이는 간단한 풀이다.
이 방법을 통해 정답이 되는 모든 연속부분수열을 찾을 수 있다.
귀류법을 통한 증명
1. 이 과정이 정답이 되는 어떤 구간 를 지나친다고 가정해보자.
2. 이 구간을 지나치는 방법은 2가지 뿐이다.
1) 가 가 되기 전에 이 를 지나친다.
이 에 도착한 순간 의 구간합은 을 넘기 때문에 는 에 도착할 때 까지 전진한다.
2) 이 가 되기 전에 가 를 지나친다.
가 에 도착한 순간 의 구간합은 보다 작기 때문에 은 에 도착할 때 까지 전진한다.
이와 같은 과정을 통해 이 방법이 최적해를 놓치지 않음을 증명할 수 있다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// N이 1인 경우가 있으므로 배열의 크기는 1칸 더 넉넉하게 잡는다.
boolean[] isPrime = new boolean[N + 2];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
ArrayList<Integer> S = new ArrayList<>();
for (int i = 2; i <= N; i++)
if (isPrime[i]) {
S.add(i);
for (int j = 2 * i; j <= N; j += i) isPrime[j] = false;
}
int ret = 0;
// 구간합은 [head, tail)이므로 초기 값은 0
int head = 0; int tail = 0; int rangeSum = 0;
while (true) {
if (rangeSum >= N) rangeSum -= S.get(head++);
else if (tail == S.size()) break;
else rangeSum += S.get(tail++);
if (rangeSum == N) ret++;
}
System.out.println(ret);
}
}