자바 - 백준 1644/ 소수의 연속합

백준 1644/ 소수의 연속합
골드3

구현 방법

이문제는 사실 제목에 풀 방향이 나와있어서 어렵지 않았다.
소수 == 소수를 구하는 알고리즘을 사용해라
연속합 == 투포인터 사용해서 부분합 구하기


처음 방식
소수 구하기 위해 "현재 판별하고자 하는 수의 제곱근보다 작은 자연수로 모두 나누기"을 이용했다.
따라서 입력값 N 범위 내의 모든 소수를 위의 방법을로 구한 뒤, 투 포인터를 이용해서 가능한 구간합의 경우의 수를 구했다.


구간합의 경우의 수 구하는 방법은 아래와 같다.

1. 시작, 끝 인덱스를 0으로 잡고, 현재까지의 구간 합을 첫번째 소수값으로 한다.
2. 만약 현재까지의 구간 합과 구하고자 하는 수가 같다면 횟수를 하나 증가시키고, 현재까지의 구간합에 시작 인덱스의 소수를 뺀다. 그후 시작 인덱스를 하나 증가시킨다. -> 다음 구간합 경우의 수를 구하기 위해
3. 만약 현재까지의 구간합이 구하고자 하는 수보다 작다면 끝 인덱스를 하나 증가시키고, 끝 인덱스가 최대 범위안에 있다면 증가시킨 끝 인덱스에 해당하는 소수를 현재까지의 구간합에 더한다. -> 현재까지의 구간합 수를 키우기 위해, 만약 끝 인덱스가 최대 범위를 초과한다면 종료한다.
4. 만약 현재까지의 구간합이 구하고자 하는 수보다 크다면 현재까지의 구간합에 시작 인덱스의 소수를 뺀다. 그후 시작 인덱스를 하나 증가시킨다. -> 현재까지의 구간합 수를 줄이기 위해
5. 2, 3, 4를 반복한다.

하지만 이 방법은 속도가 굉장히 느렸다. 소수 구하는 방법의 시간 복잡도가 O(N√N)이기 때문이다. 하지만 여기서 N의 범위가 최대 4,000,000이기 때문에 시간 초과가 발생하진 않았다.

에라토스테네스의 체
따라서 소수 구하는 방식의 시간복잡도를 낮추어야 한다. 이때 사용한 방법이 바로 에라토스테네스의 체이다.
이 방법은 현재 수가 소수인 경우, 소수의 배수들을 모두 미리 제외 시키는 방식으로 동작한다. 이 방법의 경우 시작복잡도가 O(Nlog(log N)) 이다.
구간합의 경우의 수 구하는 방법은 위와 같다.

 

주의할 점
N이 1인 경우 가능한 경우의 수가 0이다. 이 부분을 고려하지 않아서 투 포인터를 이용한 구간합 구하는 부분에서 인덱스 초과 에러가 발생했다.

 

추가로 생각해본 부분
구간합의 경우의 수 구하는 부분에서 구간 트리를 적용해보면 어떨까 고민해봤다. 하지만 구간 트리의 경우 구간에 대한 어떤 쿼리를 처리할 때는 빠르지만 현재 문제는 단순히 구간 합에 대한 경우의 수를 구하는 문제이므로 적합하지 않다고 결론 내렸다.

코드

import java.util.*;
import java.io.*;

/**
 * 백준 1644
 * 소수의 연속합
 * 골드3
 * https://www.acmicpc.net/problem/1644
 */
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());
        if(N == 1)
            System.out.println(0);
        else {
            List<Integer> l = new ArrayList<>();
            boolean[] isPrime = new boolean[N + 1];

            Arrays.fill(isPrime, true);

            isPrime[0] = false;
            isPrime[1] = false;

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

            for (int i = 2; i < N + 1; i++)
                if (isPrime[i]) {
                    l.add(i);
                }

            int start = 0;
            int end = 0;
            int sum = l.get(0);
            int count = 0;

            while(start <= end) {
                if(sum == N) {
                    count++;
                    sum -= l.get(start);
                    start++;
                } else if(sum > N) {
                    sum -= l.get(start);
                    start++;
                } else {
                    end++;
                    if(end >= l.size())
                        break;
                    sum += l.get(end);
                }
            }

            System.out.println(count);
        }
    }
}