[Baekjoon] 1644번: 소수의 연속합

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

1644번: 소수의 연속합

문제 설명

소수 구하기와 투 포인터가 결합된 문제였다. N이 주어지면 해당 N까지의 소수를 모두 구한 뒤 투 포인터를 활용해 합이 되는 연속된 합의 개수를 카운트하면 된다.

풀이 방법

소수를 구하는 방법으로는 에라토스테네스의 체를 활용한다. 이때 소수는 ArrayList에 담는다. 주의할 점은 대부분의 소수 탐색의 경우 N의 제곱근까지 수행하지만 이 문제의 경우 N까지의 소수들에 대한 연속합을 구하기 위해 ArrayList에 소수를 담아야 하므로 N까지 모든 수들을 탐색한다. for 문을 한 번 더 사용해서 첫 번째 for 문에선 소수만 구하고 두 번째 for 문에선 ArrayList에 담는 식으로 해도 되지만 그렇게 되면 O(n) 이라는 추가적인 시간복잡도가 발생하므로 한 번에 수행하도록 했다.

class Main {

    static ArrayList<Integer> primes = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        // ...
    }

    private static void init(int N) {
        boolean[] sieve = new boolean[N + 1];

        for (int i = 2; i <= N; i++) {
            if (sieve[i] == true)
                continue;

            primes.add(i);
            for (int j = i + i; j <= N; j += i) {
                sieve[j] = true;
            }
        }
    }
}

이렇게 N까지 모든 소수를 ArrayList에 담고 나면 이제 연속합을 구하면 된다.

class Main {

    static ArrayList<Integer> primes = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        // ...
    }

    private static int findSumOfPrime(int N) {
        int left = 0;
        int right = 0;
        int cnt = 0;
        int sum = 0;
        int size = primes.size();

        // 1은 소수가 아니므로 2부터 메인 로직을 수행하도록 예외처리
        if (N == 1)
            return 0;

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

        // 맨 마지막 소수가 N과 같다면 자기 자신에 대한 카운트를 하나 해준다.
        if (primes.get(right - 1) == N)
            cnt++;

        return cnt;
    }

    private static void init(int N) {
        // ...
    }
}

전체 코드는 다음과 같다.

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

class Main {

    static ArrayList<Integer> primes = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        init(N);

        int ans = findSumOfPrime(N);

        System.out.print(ans);
    }

    private static int findSumOfPrime(int N) {
        int left = 0;
        int right = 0;
        int cnt = 0;
        int sum = 0;
        int size = primes.size();

        if (N == 1)
            return 0;

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

        if (primes.get(right - 1) == N)
            cnt++;

        return cnt;
    }

    private static void init(int N) {
        boolean[] sieve = new boolean[N + 1];

        for (int i = 2; i <= N; i++) {
            if (sieve[i] == true)
                continue;

            primes.add(i);
            for (int j = i + i; j <= N; j += i) {
                sieve[j] = true;
            }
        }
    }
}