문제 1644번

소스코드

import java.io.*;
import java.util.*;
public class boj1644 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if(arr[i] ==0){
                list.add(i);
                for (int j = i; j <= n; j = j+i) {
                    arr[j] =1;
                }
            }
        }
        int answer = 0; int sum =0; int p1 =0; int p2 =0;
        while(true){
            if(sum >= n){
                sum -= list.get(p1);
                p1++;
            }else if(p2 == list.size()){
                break;
            }else if(sum<n){
                sum += list.get(p2);
                p2++;
            }
            if(sum == n){
                answer++;
            }
        }
        System.out.println(answer);
    }
}

풀이접근

1. 일단 먼저 에라토스의 채를 통해 소수는 1, 아닌 값은 0으로 만든 int 배열을 만든다.
2. 투 포인터를 통해서 결과를 구한다.

• 이 문제는 애라토스의 채를 구현할 줄만 알면 난이도에 비해서 쉽게 풀리는 문제였다.

문제핵심

• 에라토스의 채
• 투 포인터