[백준 1644] - 소수의 연속합(JAVA)

[문제] 

출처 - https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

---

[문제 풀이]

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수 들이 있다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하면 된다.

 

• 자연수가 주어지고 연속된이라는 점에서 투포인터를 사용 할 수 있다.
• N이라는 자연수가 주어졌을때 N보다 작거나 같은 소수들을 리스트에 담아야 한다.
• 에라토스테네스의 체 사용
• 투포인터를 움직일때 리스트의 범위를 잘 지켜야 한다!

 

---

[소스 코드]

 

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

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());
		ArrayList<Integer> prime = new ArrayList<>();
		boolean check[] = new boolean[n+1];
		
        
        	check[0] = check[1] = true;
        
         	//에라토스테네스의 체
        	for(int i=2; i*i<=n; i++) {
        		if(!check[i]) {
        			for(int j=i*i; j<=n; j+=i) {
        				check[j] = true;
        			}
        		}
        	}
        
        	//n보다 작거나 같은 소수를 리스트에 넣기
		for(int i=0; i<=n; i++) {
			if(!check[i]) prime.add(i);
		}
		
		int sum= (prime.size() < 0) ? 0 : prime.get(0);
		int left=0;
		int right=0;
		int ans =0;
		
		while(left <= right && right < prime.size()) {
			if(sum <= n) {
				if(sum == n) ans++;
				right++;
				if(right < prime.size()) { //증가시킨 right가 리스트 크기를 벗어나면 안됨!
					sum += prime.get(right);					
				}
			}else if(sum > n) {
				sum -= prime.get(left);
				left++;
				if(left < prime.size() && left >right) {
					left = right;
					sum = prime.get(right);
				}
			}
		}
		
		System.out.println(ans);
	}
}