[BOJ] 1644. 소수의 연속합

소수를 찾아 구간합을 구하는 문제이다.

소수를 찾는 알고리즘은 에라토스테네스의 체를 사용하였고, 구간합에 있어선 투포인터를 사용하여 쉽게 풀 수 있던 문제이다. 이 문제에서 소수의 갯수를 모르기때문에 list를 사용하여 구하였다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
 
public class Main_bj_1644_소수의연속합 {
    static int N;
    static int answer;
    static int[] arr;
    static List<Integer> primeNum;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        
        arr=new int[N+1];
        primeNum=new ArrayList<Integer>();
        
        findPrime();
        
        answer=0;
        twoPointer();
        System.out.println(answer);
        
        
    }
    
    static void findPrime() {
        //에라토스테네스의 체
        for(int i=2;i<=N;i++) {
            if(arr[i]==0) {
                primeNum.add(i);
                for(int j=i;j<=N;j=j+i) {
                    arr[j]=1;
                }
            }
        }
    }
    
    static void twoPointer() {
        int sum=0,high=0,low=0;
        while(true) {
            if(sum>=N) {
                sum-=primeNum.get(low);
                low+=1;
            }else if(high==primeNum.size()) {
                break;
            }else if(sum<N) {
                sum+=primeNum.get(high);
                high+=1;
            }
            
            if(sum==N)
                answer+=1;
            
        }
    }
}