BOJ (Java) 1644번: 소수의 연속합

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

---

풀이

연속된 소수의 합으로 n이 될 수 있는 가능성을 찾는 문제다.

주어진 숫자보다 적은 소수를 다 찾아 해당 값을 리스트에 저장한 후, 해당 리스트를 순회하며 부분합을 구했다.

부분 합 < 주어진 수라면 end 인덱스를 증가하며 부분합에 더하고

부분 합 > 주어진 수라면 start 인덱스를 증가하며 부분합에서 뺐다.

 

이 때 end 인덱스로 끝까지 탐색했을 때 부분 합 > 주어진 수라면 start 인덱스를 증가하며 주어진 수가 소수일 때를 확인했다.

---

Java 코드

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

public class Main {
    private static List<Integer> primes = new ArrayList<>();
    private static boolean[] nums;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int answer = 0;
        int N;
        N = Integer.parseInt(bf.readLine());
        nums = new boolean[N + 1];
        findPrime(N);

        int start = 0;
        int end = 0;
        int size = primes.size();

	// 슬라이딩 윈도우로 탐색
        int sum = 0;
        while (start < size && end < size) {
            if (sum <= N) {
                sum += primes.get(end++);
            } else {
                sum -= primes.get(start++);
            }

            if (sum == N) answer++;
        }
        
        // 모두 탐색 후 주어진 숫자 < 부분합이라면 한 번 더 탐색
        if (N < sum) {
            while (start < size && N < sum) {
                sum -= primes.get(start++);
            }
            if (sum == N)
                answer++;
        }

        System.out.println(answer);
    }

    // 에라토스테네스의 체를 활용, 주어진 범위에서의 소수를 구함
    private static void findPrime(int n) {
        for (int i = 2; i <= n; i++) {
            if (nums[i]) continue;

            primes.add(i);
            for (int j = i; j <= n; j += i) {
                nums[j] = true;
            }
        }
    }
}