[백준] 1644번 : 소수의 연속합 - 자바(JAVA)

 

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

1644번: 소수의 연속합

문제 해석

어떤 수 N을 소수의 합으로 나타낼 수 있다면 그 경우의 수를 구하는 문제입니다.

 

예를 들어보겠습니다.

3은 3 자기 자신으로 한 가지가 가능합니다.

41 = 2 + 3 + 5 + 7 + 11 + 13 , 11 + 13 + 17, 41으로 3가지가 가능합니다.

53 = 5+7+11+13+17 = 53으로 세 가지가 가능합니다.

 

소수를 모두 구한 다음에 해당 소수를 기반으로 투 포인터를 통해 경우의 수를 탐색하면 될 것 같습니다.

즉, 소수들의 연속된 부분합이 특정수를 만족하는 경우를 찾으면 됩니다.

 

문제 풀이 전 설계

에스테라 토스의 체를 통해 N보다 작은 소수를 모두 구합니다.

이후에 투 포인터를 활용하여 N을 만족하는 연속된 부분합의 개수를 구합니다.

 

문제 풀이하면서

에라토스테네스의 체를 구하는 과정 중에 Out of Index Error가 발생했습니다.

i*i부터 시작하도록 하자 overFlow가 발생하였기 때문에 벌어진 일이었습니다.

해당 코드를 i*2로 수정한 후 정답 처리되었습니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        //소수 탐색
        boolean[] primeArray = new boolean[N+1];
        for(int i=2; i<= N; i++){
            if(primeArray[i]){
                continue;
            }
            for(int j=2*i; j<= N; j+=i){

                if(primeArray[j]){
                    continue;
                }
                if(j % i == 0){
                    primeArray[j] = true;
                }
            }
        }
        List<Integer> primeNumbers = new ArrayList<>();

        for(int i=2; i<=N; i++){
            if(primeArray[i]){
                continue;
            }
            primeNumbers.add(i);
        }

        //소수 탐색 완료

        //투포인터 시작
        int left = 0, sum =0,result =0;
        int size = primeNumbers.size();
        for(int right=0; right < size; right++){

            sum += primeNumbers.get(right);
            if(sum == N){
                result++;
                continue;
            }

            while(sum > N && left < size){
                sum -= primeNumbers.get(left++);
                if(sum == N){
                    result++;
                    continue;
                }
            }
        }
        System.out.println(result);
    }
}