Q 1644 소수의 연속합

💡 문제 요약 및 분석

연속된 소수의 합이 N이 되는 경우의 수를 출력한다. 예를 들어 11+13+17=41 처럼 연속된 소수를 더하는 경우만 카운트한다. 3+17=20 처럼 연속되지 않은 소수를 더하는 경우는 카운트하지 않는다.

💡 알고리즘 설계

✅ 핵심 아이디어 : 소수로 이루어진 배열이 필요하다.

  1. 입력

    • 표준입력을 받아 int N 생성

  2. 연산

    • 에라토스테네스의 체 알고리즘으로 2부터 n까지의 소수 리스트 primes 를 생성한다.
    • left = 0, right = 0, sum = 0, count = 0 변수 생성.
    • while(left < primes.size()) 로 반복하면서 이하 조건에 따라 포인터를 움직이며 조건을 만족시키는 경우를 찾는다. sum < N : right++ sum > N : left++ sum == N : count++
    • 반복문 안에서 left, right 포인터 두 개 다 끝까지 가는 경우의 수도 포함해야 하기 때문에 왼쪽에 있는 left 포인터를 반복 조건으로 걸고, 오른쪽에 있는 right 포인터가 배열 사이즈를 넘어 OutOfBoundsException 이 발생하면 안되기 때문에 right 포인터의 위치가 배열의 사이즈와 일치하면 break; 하도록 했다.

  3. 출력

    • count 변수를 출력한다.

💡 코드

import java.util.*;

public class Main {

    static int read() throws Exception {
        int n = 0, c = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    // 에라토스테네스의 체
    static List<Integer> sieve(int N) {
        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        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;
    }

    public static void main(String[] args) throws Exception {
        int N = read();
        List<Integer> primes = sieve(N);

        int left = 0, right = 0, sum = 0, count = 0;
        while (left < primes.size()) {
            if (sum == N) {
                count++;
                sum -= primes.get(left);
                left++;
            } else if (sum < N) {
                if (right == primes.size()) break;
                sum += primes.get(right);
                right++;
            } else if (sum > N) {
                sum -= primes.get(left);
                left++;
            }
        }
        System.out.println(count);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도공간 복잡도
O(n)O(n)

💡 느낀점 및 기억할 정보

에라토스테네스의 체

소수 생성 알고리즘이다. 2부터 n까지의 소수를 생성하고자 할 때 매우 빠른 속도로 동작한다. 일단 2부터 n까지의 수는 모두 소수라고 가정하고, 2의 배수 3의 배수 4의 배수… 등을 하나씩 제거한다. (소수의 배수는 소수가 아니다) 그러면 남은 수들이 소수가 된다.

public static List<Integer> sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;

    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;
}

투 포인터 테크닉

1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 사용하여 목표값을 구한다. 완전탐색 O(n2) 과 비교하면 O(n) 시간으로 탐색이 가능하다. 1. 연속된 구간의 원소들을 확인해야 하거나 2. 정렬된 배열에서 특정 값을 구할 때 시도할 수 있다.

1. 연속된 구간의 원소 확인

이 경우 left, right 포인터는 배열의 0에서부터 출발한다. 배열의 부분합이 x인 경우가 몇 개인지 찾아내는 문제라고 가정해보자. ary[left] 에서 ary[right] 까지의 누적합 sum을 구하고, 이하 세 가지 조건에 맞는 경우에 포인터를 움직인다. sum < x: right++ sum > x: left++ sum == x: count++

2. 정렬된 배열에서 특정 값 구하기

정렬된 배열이라는 점이 중요하다. 이 경우 left는 0에서, right는 ary.length - 1 에서 출발한다. 배열의 특정 원소 두 개의 합이 x인 경우를 찾아내는 문제라고 가정해보자. 이하 세 가지 조건에 맞는 경우에 포인터를 움직인다. sum < x: left++ sum > x: right-- sum == x: return;