1644번 : 소수의 연속합 [Java]

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

해결 방안

먼저 에라토스테네스의 체를 사용해 N까지의 소수를 구한다. 구한 소수를 arraylist에 넣은 뒤 투포인터를 사용해 경우의 수를 구한다.

 

전체 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int N;
	static boolean[] arr;
	static ArrayList<Integer> list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new boolean[N + 1];
		list = new ArrayList<>();

		arr[0] = arr[1] = true;
		for (int i = 2; i * i <= N; i++) {
			if (!arr[i]) {
				for (int j = i * i; j <= N; j += i) {
					arr[j] = true;
				}
			}
		}

		for (int i = 1; i <= N; i++) {
			if (!arr[i])
				list.add(i);
		}

		int start = 0;
		int end = 0;
		int sum = 0;
		int ans = 0;

		while (true) {
			if (sum >= N) {
				sum -= list.get(start);
				start++;
			} else if (end == list.size()) {
				break;
			} else {
				sum += list.get(end);
				end++;
			}
			if (N == sum)
				ans++;
		}
		System.out.println(ans);
	}
}