JAVA 백준 소수의 연속합 (투 포인터)

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

---

문제

1. 입력으로 자연수 N ( 1 <= N <= 4000000 ) 을 입력받음.
2. 입력된 자연수 N을 연속된 소수의 합으로 표현할 수 있을 경우 정답으로 출력할 변수를 1 증가시킨다.
3. 모든 연속된 소수의 합을 모두 살펴보고 마지막으로 정답 변수를 출력한다.

---

 

투 포인터에 중점을 둔 문제 풀이 방법이다.

같은 지점에서 출발하여 같은 방향으로 나아가는 두 개의 포인터를 만들어 진행한다.

 

에라토스테네스의 체를 이용하여 N까지의 소수를 구한 후 ArrayList에 추가하여 1부터 N까지의 소수가 담긴 배열을 만든 뒤 시작한다.

 

0에서부터 시작해서 같은 방향으로 인덱스를 이동하며 전체를 탐색하며 조건을 비교할 수 있도록 한다.

포인트 두 개를 p1과 p2로 지정하고 p1을 먼저 이동시키며 sum 변수에 더하며 조건을 비교한다.

 

총 세 개의 조건을 비교하여 결과를 출력한다.

 

1. p1이 마지막 인덱스일 때 소수 배열에서 p1 인덱스 위치의 수가 N과 같다면 반복을 중단하도록 하여 시간을 조금이라도 아끼도록 했다.

2. 배열에서 p1 위치에 있는 수를 sum에 더하며 sum과 N을 비교한다.

3. 2에서 sum과 N을 비교할 때는 while문을 이용하여 조건을 달았는데, 이 때 사용하는 조건은 먼저 간 포인터 p1 보다 p2가 작아야 되고, sum이 N보다 크거나 같을 때 while문을 이용할 수 있도록 하였다.

while문에서는 sum과 N이 같으면 결과를 1 증가시키며, 이 조건에 관계 없이 sum에서 늦게 출발한 포인터인 p2 위치의 수를 배열에서 찾아 sum에서 빼고 p2를 1 증가시키도록 하였다.

 

 

 

최종 코드

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

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());

        int result = 0;

        boolean[] temp = new boolean[N + 1]; // 기본 설정 false
        ArrayList<Integer> primeNumber = new ArrayList<>();

        for (int i = 2; i <= N; i++) {
            if (!temp[i]) {
                primeNumber.add(i);
                for (int j = i + i; j <= N; j += i) { //소수의 배수부터 N까지 제외
                    temp[j] = true;
                }
            }
        }

        int sum = 0;
        int p2 = 0;

        for (int p1 = 0; p1 < primeNumber.size(); p1++) {
            sum += primeNumber.get(p1);
            if (p1 == primeNumber.size() - 1) {
                if (primeNumber.get(primeNumber.size() - 1) == N) {
                    result++;
                }
                break;
            }
            while (p2 <= p1 && sum >= N) {
                if (sum == N) {
                    result++;
                }
                sum -= primeNumber.get(p2);
                p2++;
            }
        }

        System.out.println(result);
    }
}