[백준 1644] 소수의 연속합

 

소수리스트를 만들어 놓고 투포인터 기법으로 수열의 합과 N을 비교한다.

 

투포인터 기법 자체가 연속된 배열을 사용하므로 문제에서 요구하는대로 풀 수 있다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        boolean prime[] = new boolean[n+1];
        for(int i=2; i<=n; i++)
            for(int j=i*2; j<=n; j+=i)
                prime[j] = true;
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=2; i<=n; i++)
            if(!prime[i]) list.add(i);
        
        int cnt = 0;
        int s = 0;
        int e = 0;
        int sum = 0;
        while(true) {
            if(sum >= n) sum -= list.get(s++);
            else if(e == list.size()) break;
            else sum += list.get(e++);
            if(sum == n) cnt++;
        }
        System.out.println(cnt);
    }
}