[알고리즘] 백준 > #1644. 소수의 연속합

문제링크

백준 #1644. 소수의 연속합

풀이방법

사실 소수를 구하는 부분을 제외하고는 백준 > #2003. 수들의 합2의 투포인터를 똑같이 적용해 해결할 수 있는 문제입니다~ 투포인터 관련해서는 위 문제풀이 링크를 참고해주세요! 두 문제 해결방법의 차이점에 대해 이야기해볼게요.

에라토스테네츠의 체

일단 소수를 구하는 방법입니다. 처음엔 이 방법을 생각도 못하고 코드를 짜서 당연히 주어진 시간을 초과했습니다 ㅋ,,

이는 수학에서 소수를 찾는 효율적인 방법이에요!
알고리즘은 다음과 같습니다.

#1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
#2) 2는 소수이므로 오른쪽에 2를 쓴다.
#3) 자기 자신을 제외한 2의 배수를 모두 지운다.
#4) 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
#5) 자기 자신을 제외한 3의 배수를 모두 지운다.
#6) 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
#7) 자기 자신을 제외한 5의 배수를 모두 지운다.
#8) 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
#9) 자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
n <= 120인 소수를 찾는 경우, 11^2 > 120이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

이 위키백과에서 좀 더 자세히 설명하고 있습니다.

이 방법을 적용하면 시간초과를 피할 수 있습니다!

자료구조

백준 > #2003. 수들의 합2에서는 n개로 원소의 개수가 입력으로 주어져서 n을 이용해 배열의 사이즈를 초기화 한 뒤 사용했습니다. 하지만 이 문제에서는 n 이하의 소수를 구해야하는데, 구하기 전에는 원소의 개수를 알 수 없죠! 그리고 풀이 내에서 start, end index로 접근하고 있습니다. 이와 같은 특징을 갖기 때문에 이 문제에서는 ArrayList 자료구조를 사용했습니다.

코드

import java.util.ArrayList;
import java.util.Scanner;

public class SumOfPrimeNumSequence {
    static ArrayList<Integer> primeNumbers = new ArrayList<>();
    static int n;
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        getPrimeNumbers();

        int start = 0, end = 0, sum = 0, result = 0;
        while((start <= end) && (end < primeNumbers.size())) {
            if (sum == n) result++;

            if (sum >= n) sum -= primeNumbers.get(start++);
            else sum += primeNumbers.get(end++);
        }

        System.out.print(result);
    }

    static private void getPrimeNumbers() {
        boolean[] primeFlag = new boolean[n + 1]; // false -> primeNum
        for (int i = 2; i * i <= n; i++) {
            if (!primeFlag[i]) { // 해당 수가 소수라면, 그 배수들은 소수가 아님(i 배수는 약수로 i를 갖기때문)
                for(int j = i * i; j <= n; j += i) primeFlag[j] = true; // i*k (k < i) 까지는 이미 검사되었으므로 j시작 값은 i*2 에서 i*i로 개선
            }
        }

        for(int i = 2; i <= n; i++){
            if(!primeFlag[i]) primeNumbers.add(i);
        }
        primeNumbers.add(0);
    }
}