백준 - 1644 소수의 연속합(Java)

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

1644번: 소수의 연속합

 

투포인터 문제입니다.

문제 자체를 해결하기 위해서는 투포인터가 필요하긴 하지만, 그 전에 소수를 만들기 위해 에라토스테네스의 체가 필요합니다.

저의 경우 다른 방법으로 소수를 만들었더니 시간초과가 났었습니다.

 

에라토스테네스의 체의 경우 https://firework-ham.tistory.com/8에 정말 자세히 나와있으니, 모르시는 분은 꼭 읽어보시기 바랍니다.

 

소수를 만들었으면 그 다음은 정말 간단합니다.

두 개의 포인터를 같은 위치에 두고 부분합이 비교하는 대상 N보다 큰지, 작은지를 비교해 포인터를 이동시키면 됩니다.

 

[구현 코드]

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        boolean[] arr = new boolean[n + 1];
        arr[0] = true;
        arr[1] = true;

        List<Integer> primes = new ArrayList<>();

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (!arr[i]) {
                for (int j = i * i; j < n + 1; j += i) { // 배수를 없앰
                    arr[j] = true;
                }
            }
        }

        for (int i = 2; i < n + 1; i++) {
            if (!arr[i]) primes.add(i);
        }

        // 다루기 편하게 하기 위해 List를 배열로 변환
        int[] pArr = Arrays.stream(primes.toArray(new Integer[0])).mapToInt(Integer::intValue).toArray();

        int lp = 0;
        int hp = 0;
        int pSum = 0;
        int cnt = 0;

        while (true) {
            if (pSum >= n) pSum -= pArr[lp++]; // 부분 합이 크기 때문에 lp를 옮김
            else if (hp == pArr.length) break;
            else pSum += pArr[hp++]; // 부분 합이 작기 때문에 hp를 옮김
            if (n == pSum) cnt++;
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}