[코딩테스트][백준] 🔥 백준 1644번 "소수의 연속합" 문제: Java으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Java 풀이시간: 20분

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        if (N == 1) {
            System.out.println(0);
            return;
        }

        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        isPrime[1] = false;
        isPrime[0] = false;

        for (int i = 2; i <= Math.sqrt(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);
            }
        }

        if (primes.isEmpty()) {
            System.out.println(0);
            return;
        }

        int startIdx = 0;
        int endIdx = 0;
        int answer = 0;
        int sum = primes.get(0);

        while (true) {
            if (sum <= N) {
                if (sum == N) {
                    answer++;
                }
                if (endIdx >= primes.size() - 1) {
                    break;
                }
                endIdx++;
                sum += primes.get(endIdx);
            } else {
                sum -= primes.get(startIdx);
                startIdx++;
                if (startIdx >= primes.size()) break;
            }
        }
        System.out.println(answer);
    }
}

단순히 에라토네스의 체(? 이름이 생각이 안난다 ㅎ) ㅋㅋ 랑 투 포인터 즉, 슬라이딩 윈도우 문제를 합한 문제이다. 소수를 먼저 구한 후, 그 소수가 정렬된 상태이기 때문에 슬라이딩 윈도우를 그대로 적용시켜주면 된다.

이렇게 Java으로 백준의 "소수의 연속합" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊