[백준] 1644번 - 소수의 연속합 [Java]

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

 

[백준] 1644번 - 소수의 연속합 [Java]

[백준] 1644번 - 소수의 연속합 [Java]

---

1.  아이디어

 

에라토스테네스의 체를 이용해서 소수를 구하고 투 포인터 알고리즘으로 연속합을 구하는 방식을 활용하면 해결할 수 있다.

---

2. 문제풀이

 

에라토스테네스의 체를 이용해서 소수 리스트를 먼저 구했다.

이후 투 포인터 알고리즘을 활용해서 소수의 연속합을 구하는데 포인터는 둘다 앞쪽에 위치시킨채 소수의 연속합이 N보다 작으면 오른쪽 포인터를 한칸 오른쪽으로, N보다 크면 왼쪽 포인터를 한칸 오른쪽으로 이동시키는 방식으로 구현했다.

N이 1일 경우 예외처리를 해줘야 했는데 그냥 main 메서드에서 바로 종료하는 방식으로 구현했다.

---

3. 코드

 

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

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

        // 1은 예외처리
        if (N == 1) {
            System.out.println(0);
            return;
        }

        List<Integer> primes = getPrimes(N);
        int left = 0;
        int right = 0;
        int sum = 0;
        int cnt = 0;

        while (true) {
            if (sum < N) {
                sum += primes.get(right++);
            } else if (sum > N) {
                sum -= primes.get(left++);
            } else {
                sum -= primes.get(left++);
                cnt++;
            }

            if (right == primes.size() && sum < N) break;
        }

        System.out.println(cnt);
    }

    private static List<Integer> getPrimes(int N) {
        boolean[] isPrime = new boolean[1 + N];
        Arrays.fill(isPrime, true);

        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) primes.add(i);
        }

        return primes;
    }

}

---

4. 후기