BOJ_1644 : 소수의 연속합

👉 문제링크

1644번: 소수의 연속합

---

 

---

🔸 문제 분석 🔸

• 정수 N을 연속된 소수의 합으로 만드는 경우의 수를 출력한다.

🔸 문제 풀이 🔸

• 소수를 구하기 위해 에라토스테네스의 체를 사용한다.
• 연속된 수의 합에서 경우의 수를 따지므로 투 포인터를 이용해 배열을 이동하며 N이 만들어지는지 확인한다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        if (N == 1) {
            bw.write('0');
            bw.flush();
            return;
        }

        // 소수 구하기 : 에라토스테네스의 체
        boolean[] primes = new boolean[N + 1];
        ArrayList<Integer> primesList = new ArrayList<>();

        for (int i = 2; i <= N; i++) {
            if (!primes[i]) {
                int mul = 2;
                while (i * mul <= N) {
                    primes[i * mul++] = true;
                }
                primesList.add(i);
            }
        }

        // 경우의 수 구하기 : 투포인터
        int left = 0;
        int right = 0;
        long sum = 2;
        int answer = 0;

        while (left <= right) {
            if (sum < N) { // 합이 작으면 오른쪽 +1
                if (++right >= primesList.size()) break;
                sum += primesList.get(right);
            } else if (sum > N) { // 합이 크면 왼쪽 -1
                sum -= primesList.get(left++);
            } else { // 같으면 카운트 1늘리고 왼쪽 -1
                answer++;
                sum -= primesList.get(left++);
            }
        }

        // Output
        bw.write(Integer.toString(answer));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 먼저 소수 목록을 구하기 위해 에라토스테네스의 체를 이용한다.
  • 소수를 찾으면 ArrayList인 primeList에 저장한다.
• primeList에 저장 된 소수 목록으로 투 포인터를 이용해 연속된 합이 N이 되는 경우의 수를 구한다.
  • 합이 N보다 작으면 right +1
  • 합이 N보다 크면 left + 1
  • 합이 N과 같으면 answer + 1 후, left + 1
• answer을 출력한다.

---

🔸 end 🔸

•  N이 1인 경우에 primeList의 크기가 0이므로 런타임 에러가 났다. 1인 경우는 예외처리 한다.
• 투 포인터와 에라토스테네스의 체 알고리즘을 떠올린 후에는 쉽게 풀이 할 수 있었다.