[BaekJoon] 1644 소수의 연속합 (Java)

1.  문제 링크

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

2.  문제

요약

• 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있지만 그렇지 않은 자연수들도 있습니다.
• 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 4,000,000보다 작거나 같은 자연수 N이 주어집니다.
• 출력: 첫 번째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int N, answer = 0;
	static ArrayList<Integer> prime;
	static int[] cumulativeSum;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		prime = new ArrayList<Integer>();
	}
	
	static void solution() {
		if(N == 1) {
			System.out.println(0);
			return;
		}
		getAllPrimes();
		cumulativeSum = new int[prime.size() + 1];
		cumulative();
		twoPointer();
		System.out.println(answer);
	}
	
	static void twoPointer() {
		for(int L = 0, R = 1; L < cumulativeSum.length; L++) {
			while(L < R && R < cumulativeSum.length) {
				int dif = cumulativeSum[R] - cumulativeSum[L];
				if(dif == N) {
					answer++;
					break;
				}
				if(dif > N) break;
				if(dif < N) R++;
			}
		}
	}
	
	static void cumulative() {
		for(int index = 1; index <= prime.size(); index++)
			cumulativeSum[index] = prime.get(index - 1);
		for(int index = 1; index <= prime.size(); index++)
			cumulativeSum[index] += cumulativeSum[index - 1];
	}
	
	static void getAllPrimes() {
		boolean[] primes = new boolean[N + 1];
		primes[0] = primes[1] = true;
		for(int num = 2; num <= Math.sqrt(N); num++) {
			if(!primes[num]) {
				for(int n = num * num; n <= N; n += num) primes[n] = true;
			}
		}
		for(int num = 2; num <= N; num++) {
			if(!primes[num]) prime.add(num);
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 이 문제는 투포인터를 이용하여 구할 수 있는 문제입니다.
• 주어진 N 이하의 모든 소수들을 먼저 찾고 이를 이용하여 연속된 소수의 합으로 나타낼 수 있는지 확인을 하는데, 이 때 에라토스테네스의 체를 이용하여 모든 소수들을 구합니다.

static void getAllPrimes() {
	boolean[] primes = new boolean[N + 1];
	primes[0] = primes[1] = true;
	for(int num = 2; num <= Math.sqrt(N); num++) {
		if(!primes[num]) {
			for(int n = num * num; n <= N; n += num) primes[n] = true;
		}
	}
	for(int num = 2; num <= N; num++) {
		if(!primes[num]) prime.add(num);
	}
}

• 위에서 구한 모든 소수들에 대해 누적 합을 진행합니다.

static void cumulative() {
	for(int index = 1; index <= prime.size(); index++)
		cumulativeSum[index] = prime.get(index - 1);
	for(int index = 1; index <= prime.size(); index++)
		cumulativeSum[index] += cumulativeSum[index - 1];
}

• 위에서 구한 누적 합을 이용해 앞에서부터 포인터를 하나씩 이동하면서 왼쪽 포인터에 해당하는 소수부터 오른쪽 포인터에 해당하는 소수까지의 합을 구합니다.
• 만약 이 합이 주어진 N과 같다면 개수를 하나 추가시키고 포인터를 이동하여 다른 조합을 찾습니다.

static void twoPointer() {
	for(int L = 0, R = 1; L < cumulativeSum.length; L++) {
		while(L < R && R < cumulativeSum.length) {
			int dif = cumulativeSum[R] - cumulativeSum[L];
			if(dif == N) {
				answer++;
				break;
			}
			if(dif > N) break;
			if(dif < N) R++;
		}
	}
}