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

문제

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

풀이

소수를 구하는 방법과 투 포인터를 활용하여 문제를 풀었다.

1. 소수 구하기

   에라토스테네스의 체를 활용하여 소수를 구하였다.

   for (int i = 2; i <= n; i++) {
           if (array[i] == 0) {
               list.add(i);
               for (int j = i; j <= n; j = i + j){
                   array[j] = 1;
               }
           }
       }

   입력받은 n까지의 배열을 만들고 2부터 n까지 for문을 돈다.
   이 과정에서 array[]의 값이 0이면 list에 값을 담고 그 수의 배수에 있는 배열의 값을 1로 변경해준다.

2. 투 포인터 사용하기

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        int[] array = new int[n + 1];
        List<Integer> list = new ArrayList<>();

        for (int i = 2; i <= n; i++) {
            if (array[i] == 0) {
                list.add(i);
                for (int j = i; j <= n; j = i + j){
                    array[j] = 1;
                }
            }
        }
        int lt = 0, sum = 0;
        for (int rt : list) {
            sum += rt;
            if (sum == n) count++;
            while (sum >= n) {
                sum -= list.get(lt++);
                if (sum == n) count++;
            }
        }
        System.out.println(count);
    }
}