[알고리즘][X] 소수의 연속합

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	static int N;
	static boolean[] isPrime;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		isPrime = new boolean[N+1];
		Arrays.fill(isPrime, true);
		eratones_filter();

		// 소수 리스트에 넣어주기
		List<Integer> prime = new ArrayList<>();
		for (int i = 2; i < isPrime.length; i++) {
			if (isPrime[i]) {
				prime.add(i);
			}
		}
		
		// 투포인터 이용해서 N이 나오는지 확인
		int result = 0;

		int start = 0;
		int end = 0;
		
		if (prime.isEmpty()) {
			System.out.println(0);
			return;
		}
		int sum = prime.get(0);
		while (start <= end) {
			if (sum == N) {
				result++;
				end++;
				if (end >= prime.size()) {
					break;
				}
				sum += prime.get(end);
			} else if (sum < N) {
				end++;
				if (end >= prime.size()) {
					break;
				}
				sum += prime.get(end);
			} else {
				sum -= prime.get(start);
				start++;
			}
		}
		
		System.out.println(result);
	}

	private static void eratones_filter() {
		for (int i = 2; i <= (int) Math.sqrt(N); i++) {
			if (!isPrime[i]) {
				continue;
			}
			int j = 2;
			while (i * j <= N) {
				isPrime[i * j] = false;
				j++;
			}
		}
	}
	
	
}

- 리스트를 활용해서 푼 풀이

- 리스트를 사용하면 0일때의 예외처리가 어려워진다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int N;
	static boolean[] isPrime;
	static int[] prime = new int[283147];
	static int primeCnt = 0;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		isPrime = new boolean[N+1];
		Arrays.fill(isPrime, true);
		eratones_filter();
		
		// 소수 리스트에 넣어주기
		for (int i = 2; i < isPrime.length; i++) {
			if (isPrime[i]) {
				prime[primeCnt++] = i;
			}
		}
		// 투포인터 이용해서 N이 나오는지 확인
		int result = 0;

		int start = 0;
		int end = 0;

		int sum = prime[0];
		while (end < primeCnt) {
			if (sum < N) {
				end++;
				sum += prime[end];
				continue;
			}

			if (sum == N) {
				result++;
			}
			
			sum -= prime[start];
			start++;
		}
		
		System.out.println(result);
	}

	private static void eratones_filter() {
		for (int i = 2; i <= (int) Math.sqrt(N); i++) {
			if (!isPrime[i]) {
				continue;
			}
			int j = 2;
			while (i * j <= N) {
				isPrime[i * j] = false;
				j++;
			}
		}
	}
	
	
}

- 배열을 이용하면 0일때라도 nullPointerException이 생기진 않는다.

- 또한 end가 사이즈보다 커질 때에도 NullPointerException이 생기지 않는다. 왜냐하면 배열의 크기를 이미 충분하게 잡아놓았기 때문이다.

package boj.solution1644;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int N;
	static boolean[] isPrime;
	static int[] prime = new int[283147];
	static int primeCnt = 0;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		isPrime = new boolean[N+1];
		Arrays.fill(isPrime, true);
		eratones_filter();
		
		// 소수 리스트에 넣어주기
		for (int i = 2; i < isPrime.length; i++) {
			if (isPrime[i]) {
				prime[primeCnt++] = i;
			}
		}
		// 투포인터 이용해서 N이 나오는지 확인
		int result = 0;

		int start = 0;
		int end = 0;

		int sum = prime[0];

		while (end < primeCnt) {
			if (sum > N) {
				sum -= prime[start];
				start++;
				continue;
			}
			
			if (sum == N) {
				result++;
			}
			
			end++;
			sum += prime[end];
		}
		
		System.out.println(result);
	}

	private static void eratones_filter() {
		for (int i = 2; i <= (int) Math.sqrt(N); i++) {
			if (!isPrime[i]) {
				continue;
			}
			int j = 2;
			while (i * j <= N) {
				isPrime[i * j] = false;
				j++;
			}
		}
	}
	
	
}

- start를 움직이든지 end를 움직이든지 사실 상관없다!