백준1644: 소수의 연속합 (Java, 에라토스테네스의 체, 투포인터)

☑️ 문제 링크

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

☑️ 문제 분석

• 문제 설명에 따르면 자연수 N이 주어졌을 때 해당 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제이다. 여기서 핵심은 ‘연속된’이다!!!
• 예를 들어, N이 41일 때 출력되는 경우의 수는 3가지이다.
  • 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 예를 들어, N이 20일 때,
  • 7+13 와 같이 소수의 합으로 계산이 되지만 7과 13은 연속된 소수의 합이 아니기 때문에 경우의 수에 포함될 수 없다.
  • 3+5+5+7 와 같이 5라는 소수가 중복되어 계산되기 때문에 경우의 수에 포함될 수 없다.

---

위 문제의 조건들을 읽고 생각난 풀이 방식은

1. 에라토스테네스의 체를 이용하여 1~N사이의 수 중에 소수 배열을 생성하고
2. 해당 소수 배열을 이용하여 구간합 배열을 생성한다.
3. 이후 투포인터를 사용하여 구간합이 N이 되는 경우의 수를 모두 카운트 해주는 것이다.

---

✔️관련 알고리즘 개념 - 에라토스테네스의 체

1. 구하고자 하는 소수의 범위 만큼 1차원 배열을 생성한다. 1은 소수가 아니므로 삭제하고 2부터 시작한다.
   1. 예) 1부터 30까지의 수 중 소수 구하기 ⇒ 30까지의 범위만큼 1차원 배열을 생성한다.
   

2. 선택한 수의 배수를 모두 삭제한다. ⇒ 현재는 2를 가르키고 있는데 2를 제외한 2의 배수들을 모두 삭제한다.
   

3. 다음 지워지지 않은 수를 선택한다. ⇒ 3을 선택하고 선택한 수의 모든 배수를 삭제한다. 이미 지운수는 다시 지우지 않는다.
   
   

4. 앞의 과정을 배열의 끝까지 반복한다.
   

5. 삭제되지 않은 수를 모두 출력한다.
   

• 즉, 1부터 30까지의 수 중 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29이다.

---

위의 1~3까지의 과정을 예시 입력3인 N이 41일 때를 예시로 설명해보면,

1. 에라토스테네스의 체를 사용하여 1~41사이의 소수 배열을 찾는다.
   

2. 해당 소수 배열을 이용하여 구간합 배열을 생성한다.
   

3. 이후 투포인터를 사용하여 구간합이 N이 되는 경우의 수를 모두 카운트 해주는 것이다.
   
   
   
   
   

☑️ 코드

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 자연수
        int[] p = new int[n+1];
        List<Integer> prime = new ArrayList<>();

        // 1에서 N까지의 숫자 배열 생성
        for (int i = 2; i <= n; i++) {
            p[i] = i;
        }

        // 에라토스테네스의 체를 통해 소수만 골라내기 (2부터 n의 제곱근까지 배수 탐색하면서 지우기)
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (p[i] == 0) continue;
            for (int j = i + i; j <= n; j += i) {
                p[j] = 0; // 배수 지우기
            }
        }

        // 지워지지 않은 값들로 구간합 배열 생성하기
        for (int i = 2; i <= n; i++) {
            if(p[i] != 0) prime.add(i);
        }

        // 구간합
        int[] A = new int[prime.size() + 1];
        for (int i = 1; i <= prime.size(); i++) {
            A[i] = A[i-1] + prime.get(i-1);
        }

        int count = 0; // 연속된 소수의 합으로 나타낼 수 있는 경우의 수
        int start = 0, last = 1; // 투포인터

        while(start < last && last < A.length) {
            int sum = A[last] - A[start];
            if (sum < n) {
                last++;
            } else if (sum > n) {
                start++;
            } else {
                count++;
                start++;
                last++;
            }
        }

        System.out.println(count);
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 여러가지 배열의 인덱스값 초과 문제 해결이 어려웠다.