[백준] 1644번 소수의 연속합 (자바 풀이)

문제

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

1644번: 소수의 연속합

풀이

이 문제는 에라토스테네스의 체로 소수를 구한 다음, 투 포인터 알고리즘을 사용하는 것이 핵심이다.

 

먼저 에라토스테네스의 체를 사용하여, N까지의 모든 소수를 저장한다. 

이후 투 포인터 알고리즘을 사용하기 위해 left 포인터와 right 포인터를 0으로 초기화한다.

어떤 수든 첫번째 소수는 2기 때문에 sum=2로 초기화해준다.

 

만약 sum이 N과 같다면 ans를 1 증가시키고, N보다 작다면 right 포인터를 오른쪽으로 한 칸 옮기고 sum에 올려준다.

N보다 크다면 left 포인터가 가리키는 값을 감소시키고 left 포인터를 오른쪽으로 한 칸 옮긴다.

 

자세한 내용은 다음과 같다.

위와 같은 식으로 left 포인터와 right 포인터를 잘 조정해주며 계산하면 된다.

 

코드

import java.io.*;
import java.util.*;
 
public class Baekjoon_1644 {
    static int n;
    static ArrayList<Integer> prime = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        getPrime(n);
        
        int left=0, right=0;
        int ans = 0, sum=2;
        int size = prime.size();
        
        while( left<size && right < size ) {
            if(sum == n) {
                ans++;
                sum -= prime.get(left);
                left++;
            }
            else if(sum >n) {
                sum -= prime.get(left);
                left++;
            }else {
                right++;
                if(right >= size) break;
                sum += prime.get(right);
            }
        }
        
        System.out.println(ans);
        
        sc.close();
    }
    
    /* 에라토스테네스의 체를 이용하여 소수 구하기 */
    static void getPrime(int n) {
        int temp[] = new int[n+1];
        int rootN = (int)Math.sqrt(n);
        for(int i=2; i<=n; i++) {
            temp[i] = i;
        }
        for(int i=2; i<=rootN; i++) {
            if(temp[i] != 0 ) {
                for(int j=i+i; j<=n; j+=i) {
                    temp[j] = 0;
                }
            }
        }
        for(int i=2; i<=n; i++) {
            if(temp[i] != 0) {
                //System.out.println(temp[i]); 디버깅용
                prime.add(temp[i]);
            }
        }    
    }
}
 

결과