백준 1644. 소수의 연속합

문제 : 백준 1644. 소수의 연속합

연속된 소수들을 합하여 입력 받은 n을 구할 수 있는 경우의 수를 구하는 코드를 작성하시오.

풀이

연속된 소수들의 합이라니 대놓고 누적합 이용하라고 한다.
앞의 소수들부터 더해주다가 n이 되면 count를 증가시켜준다.
반면에 소수들의 합 sum이 n보다 커지면 이전에 더한 소수들을 하나씩 빼면서 조건을 만족시키는 경우를 찾아나가는 것이다.
이 과정에서 투포인터 기법을 사용하기 때문에 문제의 분류에 투포인터도 포함되어 있다.

문제를 해결하면서 크게 어렵게 생각한 점은 없고, 강사님 풀이와 내 풀이의 차이점은 나는 ArrayList를 사용하였고 강사님은 배열을 사용했다는 점이다.
큰 차이는 없지만 간결함의 차이 정도? 참고하도록 두 해결 코드 모두 포함하였다.

내 코드

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

public class boj1644 {

    static int N = 4000000;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(br.readLine());

        ArrayList<Integer> primeNums = new ArrayList<>();

        // 수가 소수인지 아닌지를 판별하는 배열 생성
        boolean[] isPrime = new boolean[N + 1];
        for (int i = 2; i * i <= N; i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = true;
                }
            }
        }

        primeNums.add(1);

        for (int i = 2; i <= input; i++) {
            if (!isPrime[i]) {
                primeNums.add(i); // 소수 집합 생성
            }
        } // 여기까지 사전작업
        int start = 1;
        int end = 1;

        int sum = 0;
        if (primeNums.size() >= 2)
            sum = primeNums.get(start); //초기값 설정

        int answer = 0;

        while (end < primeNums.size()) {
            if (sum >= input) {
                if (sum == input) {
                    answer += 1;
                }
                sum -= primeNums.get(start);
                start++;
            }
            else {
                end += 1;
                if (end == primeNums.size())
                    break;
                sum += primeNums.get(end);
            }
        }
        System.out.println(answer);
    }
}

강사님 코드

import java.util.Scanner;

public class Main {

    static int n,cnt;
    static int P[] = new int[4000001];
    static int Plist[] = new int[1000001],Pcnt,l,r,sum;

    public static void main(String[] args) throws Exception {

        int i,j;
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        for(i=2;i<=n;i++)
        {
            if(P[i]==0)
            {
                Plist[++Pcnt] = i;
                for(j=i+i;j<=n;j+=i)
                {
                    P[j]=1;
                }
            }
        }

        l=r=1;sum = Plist[1];
        while(r<=Pcnt)
        {
            if(sum >= n)
            {
                if(sum==n)
                {
                    cnt++;
                }
                sum-=Plist[l];
                l++;
            }
            else if(sum < n)
            {
                r++;
                sum+=Plist[r];
            }
        }

        System.out.println(cnt);

        sc.close();
    }
}