[백준] 1644번 소수의 연속합(java)

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

1644번: 소수의 연속합

핵심

우선 소수를 리스트에 담아야 한다. 그러기 위해서는 소수를 찾아야 하는데,

단순한 방법으로 찾게 되면 너무 많은 시간이 걸리게 된다. 따라서 에라토스테네스의 체를 사용해야 한다.

이를 활용해 투포인트를 사용하면 쉽게 구할 수 있다.

 

 

정답 코드

import java.util.*;


public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> List = new ArrayList<>();
        boolean[] notPrime = new boolean[4000000];
        notPrime[1] = true;
        for(int i = 2; i < 2000000; i++){
            for(int j = 2; i*j<4000000; j++){
                notPrime[j*i] = true;
            }
        }
        for(int i = 1; i < 4000000; i++){
            if(!notPrime[i])List.add(i);
        }

        int count = 0;
        int start = -1;
        int sum = 0;
        loop : for(int i = 0; i < List.size(); i++){
            sum+=List.get(i);
            if(sum>=n){
                while(sum>=n){
                    if(sum==n)count++;
                    start++;
                    sum-=List.get(start);
                    if(start>i)break loop;
                }
            }
        }
        System.out.println(count);
    }
}

해설

우선 소수가 아닌 것을 탐색한다.

에라토스테네스의 체를 활용한다. 

사실 notPrime이라는 네이밍이 마음에 들지 않는다.

이유는 리스트에 소수를 담을 때! notPrime을 찾아야 하기  때문에 부정의 부정이 된다.

하지만 Prime으로 바꾸면 처음에 배열을 전부 true로 초기화해야 하는 단점이 있기 때문에 위와 같은 네이밍을 선택했다.

이후 투 포인터를 사용하여 연속합이 n과 같다면 count를 증가시킨다.

또한 아래 break 포인트가 의미하는 바는 연속된 1가지의 수가 n을 넘을 경우 더 이상의 탐색은 무의미하기 때문에

loop를 탈출하도록 만들었다.

 

 

배운 점

여태까지 배운 것을 모두 활용해야 풀 수 있는 문제이다.

이 문제를 처음 풀 때 97 퍼에서 틀렸다는 메시지를 받았다.

이유가 무엇일까 고민하다가 1이 소수가 아니라는 사실을 인지하지 못하고 있었다.

이러한 간단한 조건도 섬세하게 생각해야겠다.