백준 소수의 연속합(1644)

소수의 연속합

라이 블로그 풀이

BOJ 부분합(1806) 과 마찬가지로 투 포인터 문제인데 이번엔 종만북 풀이가 아닌 라이님의 풀이를 참고하였다.

연속부분수열의 합은 최대 $N$이므로 수열의 원소가 될 소수는 최대 $N$임을 알 수 있다. 소수는 자연수이므로 임의의 연속부분수열의 합이 $N$이 되게 하는 경우의 수는 투 포인터 알고리즘을 이용해서 해결이 가능하다. 소수는 에라토스테네스의 체 알고리즘을 사용해서 $O(N)$에 $N$이하의 소수를 모두 구한다.

종만북 풀이에서는 후보 구간을 정의하고 후보 구간들을 관찰함을 통해 $head$가 증가할 때 $tail$이 감소하는 경우는 없음을 발견하고 이를 증명했었다.

이 풀이는 구간의 합이 $N$보다 작으면 $tail$을 전진시켜서 구간의 합을 늘리고, $N$보다 크면 $head$를 전진시켜서 합을 줄이는 간단한 풀이다.
이 방법을 통해 정답이 되는 모든 연속부분수열을 찾을 수 있다.

귀류법을 통한 증명
1. 이 과정이 정답이 되는 어떤 구간 $[p, q)$를 지나친다고 가정해보자.
2. 이 구간을 지나치는 방법은 2가지 뿐이다.
1) $head$가 $p$가 되기 전에 $tail$이 $q$를 지나친다.
$tail$이 $q$에 도착한 순간 $[head, tail )$의 구간합은 $N$을 넘기 때문에 $head$는 $p$에 도착할 때 까지 전진한다.

2) $tail$이 $q$가 되기 전에 $head$가 $p$를 지나친다.
$head$가 $p$에 도착한 순간 $[head, tail )$의 구간합은 $N$보다 작기 때문에 $tail$은 $q$에 도착할 때 까지 전진한다.

이와 같은 과정을 통해 이 방법이 최적해를 놓치지 않음을 증명할 수 있다.

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);
	}

}