백준 1644 (소수의 연속합)*

문제

---

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

 

풀이

---

소수를 하나씩 판단하면서 더해가는 완전탐색을 하였더니 시간초과가 났다.

 

소수를 미리 다 찾아놓는 에라토스 테네스의 체를 이용하였다.

primeNumber = new boolean[n + 1];
for(int i = 2 ; i * i <= n ; i++) {
	if(primeNumber[i])
		continue;
	for(int j = i * i ; j <= n ; j += i) {
		primeNumber[j] = true;
	}
}

앞서 소수찾기에서 찾는 방식인 제곱근까지의 수가 소수면 해당 숫자도 소수기 때문에, 해당수의 제곱수부터 배수까지는 무조건 소수가 아닌점을 이용하여 boolean 값을 true로 바꿔줬다.

 

이렇게 에라토스테네스의체를 완성한 뒤 이분탐색을 하였다. 기존의 이분탐색과 다른점은 양쪽 끝의 포인터를 두는 것이 아닌 이문제에서는 구간합을 구하는 것이기 때문에 구간을 하나씩 늘려나갔다.

 

int left = 0, right = 0, sum = 0;
while(true) {
	if(sum >= n ) {
		sum -= primeArr[left++];
	}
	else if(right == index) {
		break;
	}
	else if(sum < n) {
		sum += primeArr[right++];
	}
				
	if(sum == n)
		answer++;
}

구간합이 n 보다 같거나 크면 구간의 제일 앞 소수를 빼준다.

구간합이 n 보다 작으면 다음 구간의 소수를 더해준다.

구간합이 n 과 같으면 값을 하나 추가한다.

구간의 끝에 도달하였으면 반복문을 종료한다.

 

위와같은 방식으로 풀었다.

 

 

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static int n;
	static long answer = 0;
	static boolean[] primeNumber;
	static int[] primeArr = new int[4000000];
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(bufferedReader.readLine());
		
		primeNumber = new boolean[n + 1];
		for(int i = 2 ; i * i <= n ; i++) {
			if(primeNumber[i])
				continue;
			for(int j = i * i ; j <= n ; j += i) {
				primeNumber[j] = true;
			}
		}
		
		int index = 0;
		for(int i = 2; i <= n ; i++) {
			if(!primeNumber[i]) {
				primeArr[index] = i;
				index++;
			}
				
		}
		
		int left = 0, right = 0, sum = 0;
		while(true) {
			if(sum >= n ) {
				sum -= primeArr[left++];
			}
			else if(right == index) {
				break;
			}
			else if(sum < n) {
				sum += primeArr[right++];
			}
			
			
			if(sum == n)
				answer++;
		}
		
		sb.append(answer);
		System.out.println(sb);
	}	
}