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

문제

 

 

접근 방식

주어진 수 n까지의 소수를 모두 구한 후에 투 포인터를 사용해

첫 번째 소수부터 기준으로 합이 n과 같거나 커질 때까지 수들을 합해주고

합이 n과 같은 경우에는 카운트를 1 증가시켜 주면서

현재 기준점이 끝날 때마다 합에서 현재 값을 빼준 후에

다음 기준점으로 넘어가면서 계산해 주면 된다.

a = {2 3 5 7 11 13 17 23 29 31 37 41}

 

n이 41일 때를 예로 들면, 2 ~ 41까지의 소수는 위와 같다.

sum		a[i]	count
2		2		1
5		3		2
10		5		3
17		7		4
28		11		5
41		13		6		v

39		-2		5
56		17		6		x
53		-3		5
48		-5		4
41		-7		3		v

30		-11		2
53		23		3		x
40		-13		2
69		29		3		x
52		-17		2		x
29		-23		1
60		31		2		x
31		-29		1
68		37		2		x
37		-31		1
78		41		2		x
41		-37		1		v

 

위의 과정을 살펴보면 2 ~ 13까지의 소수를 연속으로 더했을 때 41이 되니

카운트를 1 증가시켜 준 후에 다음 소수인 3부터 시작하기 위해 누적합에서 2를 뺀 후에

41 이상이 될 때까지 더하면 되고, 이 과정들을 반복해 주면  된다.

풀이

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());
		int size = 0;
		int count = 0;

		if (n == 1) {
			System.out.println(count);
			return;
		}

		boolean[] isPrime = new boolean[n + 1];
		int[] arr = new int[n + 1];
		int idx = 0;

		for (int i = 2; i <= n; i++) {
			if (!isPrime[i]) {
				size++;
				arr[idx++] = i;
				for (int j = i * 2; j <= n; j+=i) {
					isPrime[j] = true;
				}
			}
		}

		int end = 1;
		int sum = arr[0];

		for (int start = 0; start < size; start++) {
			while (sum < n && end < size) {
				sum += arr[end++];
			}

			if (sum == n) count++;

			sum -= arr[start];
		}

		System.out.println(count);
	}
}