[BOJ 1644] 소수의 연속합 (Java)

BOJ 1644 소수의 연속합

난이도 : 골드 3

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

1644번: 소수의 연속합

 

전략

매번 소수 판별을 하는 것보다 전처리를 하여 N 이하의 소수 목록을 만들어놓는 것이 유리하다.

따라서 에라토스테네스의 체를 이용하여 ArrayList에 소수들을 저장한 뒤에 투 포인터를 사용한 부분합 탐색을 진행했다.

 

시행착오

N의 최소 범위인 1이 입력되었을 때 빈 ArrayList에 index로 접근하면서 IndexOutOfBoundsException이 발생했다.

따라서 이를 확인하는 코드를 추가하였다.

 

코드

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        boolean[] isPrime = new boolean[N + 1];
        for (int i=2; i<=N; i++)
            isPrime[i] = true;

        for (int i=2; i*i<=N; i++) {
            if (isPrime[i])
                for (int j=i*i; j<=N; j+=i)
                    isPrime[j] = false;
        }

        ArrayList<Integer> primes = new ArrayList<>();
        for (int i=2; i<=N; i++)
            if (isPrime[i])
                primes.add(i);

        if (primes.size() < 1) {
            System.out.println(0);
            return;
        }

        int cnt = 0;

        int start = 0;
        int end = 0;
        int sum = primes.get(start);

        for (; start < primes.size(); start++) {
            while (sum < N && end < primes.size() - 1)
                sum += primes.get(++end);

            if (sum == N)
                cnt += 1;

            sum -= primes.get(start);
        }

        System.out.println(cnt);
    }
}