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

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

1644번: 소수의 연속합

 

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

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());

        boolean check[] = new boolean[n+1];
        ArrayList<Integer> primes = new ArrayList<>();

        // 소수가 아니면 true로
        check[0] = check[1] = true;

        for(int i=2; i <= Math.sqrt(check.length); i++){
            for(int j=i*i; j<=n; j+=i){
                if(!check[j]) check[j] = true;
            }
        }
        for(int i=0; i<=n; i++){
            if(!check[i]) primes.add(i); // 소수 넣기
        }

        int sum = 0, left = 0, answer = 0;

        for(int right = 0; right<n; right++){
            if(right >= primes.size()) continue;

            sum += primes.get(right);

            if(sum == n) answer++;

            while(sum >= n && left >=0){ // sum 보다 같거나 작으면 left인덱스 증가해 해당 값 빼줌
                sum -= primes.get(left++);
                if(sum == n) answer++;
            }
        }
        System.out.println(answer);


    }
}

 

 

에라토스테네체로 소수를 판별한 다음에 primes 리스트에 넣는다.

그 후에 투포인터로 합이 n이 되는 부분수열의 개수를 구하면 된다.