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

문제

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

 

접근 방법

1. N을 연속된 소수의 합으로 몇가지 방법이 있는지를 구하는 문제이다.
2. 따라서 소수를 에라토스테네스의체로 list에 넣어두었다.
3. 또한 연속된 수의 합은 사실 브루트포스로 가능하지만 시간초과가 발생하는것을 방지하기 위해 투포인터로 구했다.
4. 소수를 리스트에 넣어놨기 때문에 N이 400만일걸 예상하여 list.get(s)+list.get(e) < N 일때 포인터가 리스트 인덱스를 초과하지 않도록 예외를 넣어주었다.

코드

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

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N;
    private static boolean[] isPrime = new boolean[4000010];
    private static ArrayList<Integer> list = new ArrayList<Integer>();
    
    //에라토스테네스의 체
    public static void primeCheck(){
        isPrime[0] = false;
        isPrime[1] = false;

        for(long i = 2 ; i <= 4000000 ; i++){
            if(isPrime[(int)i]){
                for(long j = i*i ; j <= 4000000 ; j+=i){
                    isPrime[(int) j] = false;
                }
            }
        }

        for(int i = 2 ; i <=4000000 ; i++){
            if(isPrime[i]) list.add(i);
        }
    }

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        Arrays.fill(isPrime,true);

        primeCheck();
//        System.out.println(list);
    }

    //실행
    public static void process() {
        int s = 0;
        int e = 0;
        int sum = list.get(0);
        int count = 0;
        int size = list.size();

        while(s<=e){
            if(sum==N){
                count++;
                sum-=list.get(s);
                s++;
            }else if(sum < N){
                e++;
                
                //e가 인덱스를 초과하는것을 방지
                if(e == size) break;
                
                sum+=list.get(e);
            }else if(sum > N){
                sum-=list.get(s);
                s++;
            }
        }
        System.out.println(count);

    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}