[BOJ] 1644 소수의 연속합 Java 풀이

BOJ 1644 소수의 연속합

 

소수에 대한 개념과 투 포인터에 대해 익숙하다면 크게 어렵지 않게 해결할 수 있는 문제다.

소수의 특성 중 '양의 정수'라는 점과 문제에서 주어진 '연속된 소수'라는 점을 활용해 투 포인터를 사용하면 된다.

풀이는 에라토스테네스의 체를 이용해 주어진 범위(N <= 4,000,000)까지의 모든 소수를 미리 구해놓고, 첫 번째 소수인 2부터 N보다 작은 소수까지 투 포인터로 연속합의 범위를 움직여보면서 N과 비교를 해주는 것이다.

비교를 통해서 1) N보다 작으면 연속합의 범위를 우측으로 확장시키고,
2) 동일하다면 답으로 출력할 cnt를 하나씩 증가시킴과 동시에 전체 범위를 우측으로 하나씩 이동한다.
3) N보다 크면 범위의 가장 작은 값을 제거해 연속합의 범위를 축소시킨다.

* 에라토스테네스의 체 범위를 500만으로 잡은 이유는 별 의미 없고, 문제에서 주어진 N의 범위보다 넉넉히 설정하려는 의도이다
* 에라토스테네스의 체 시간복잡도: O(N loglog N)
* 투포인터 시간복잡도: O(N)

package exhaustiveSearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class P1644 {
	static int N;
	static ArrayList<Integer> primes = new ArrayList<>();
	static boolean[] isNotPrime;
	static int cnt;
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		isNotPrime = new boolean[5000000];
		isNotPrime[1] = true;
		
		// 에라토스테네스의 체
		for(int i = 2; i*i < 5000000; i++) {
			for(int j = i*i; j < 5000000; j+=i) {
				isNotPrime[j] = true;
			}
		}
		for(int i = 1; i < 5000000; i++) {
			if(isNotPrime[i] == false) {
				primes.add(i);
			}
		}
		
		// two pointer
		int start = 0; int end = 0; int sum = primes.get(0);
		cnt = 0;
		while(true) {
			if(sum == N) {
				cnt++;
				sum += primes.get(++end);
				sum -= primes.get(start++);
			}else if(sum < N) {
				sum += primes.get(++end);
			}else {
				sum -= primes.get(start++);
			}
			
			if(primes.get(end) > N) {
				break;
			}
		}
		
		System.out.println(cnt);
		
	}

}