[백준] 1644. 소수의 연속합 (Java)

 

문제

1644번: 소수의 연속합

 

 

알고리즘

에라토스테네스의 체, 투 포인터

 

풀이

에라토스테네스의 체를 이용해 N 이하의 소수를 리스트에 삽입하고,

투 포인터를 이용해 O(N) 의 시간복잡도로 경우의 수를 구한다.

 

---

에라토스테네스의 체를 이용한 소수 판별

 

소수인지 저장할 N+1 크기의 boolean형 변수 prime을 선언한다.

prime은 2부터 N까지 모두 true로 초기화한 상태로, 즉 모두 소수라고 가정한 상태로 시작한다.

 

i를 2부터 N의 제곱근까지 1씩 증가시키며

만약 i가 소수라면 i의 배수는 i를 약수로 가지기 때문에 모두 합성수로 변경한다.

 

N의 제곱근까지 수행하는 이유는 N의 약수 중 하나는 반드시 N의 제곱근보다 작거나 같기 때문이다.

 

---

투 포인터를 이용한 경우의 수 확인

 

두 개의 포인터 start, end 모두 0을 시작으로 한다.

따라서 sum은 primes의 첫번째 인덱스 값으로 초기화한다.

 

1. sum이 N과 같다면 count를 1 증가시킨다.

2-1. sum이 N보다 작거나 같다면 end를 1 늘려 sum 을 증가시키고

2-2. sum이 N보다 크다면 left를 1 늘려 sum을 감소시킨다.

 

만약 end 를 더 이상 늘릴 수 없을 경우 가능한 경우의 수를 모두 탐색한 것이므로 count를 출력한다.

 

 

코드

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

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

		int N = Integer.parseInt(br.readLine());
		if (N == 1) {
			System.out.println(0);
			return;
		}

		List<Integer> primes = getPrimes(N);

		int start = 0;
		int end = 0;
		int sum = primes.get(0);
		int count = 0;

		while (true) {
			if (sum == N)
				count++;

			if (sum <= N) {
				if (end == primes.size() - 1) break;
				sum += primes.get(++end);
			} 
			else if (sum > N) {
				sum -= primes.get(start++);
			}	
		}

		System.out.println(count);
	}

	private static List<Integer> getPrimes(int n) {

		List<Integer> list = new ArrayList<>();

		boolean[] prime = new boolean[n + 1];
		for (int i = 2; i <= n; i++)
			prime[i] = true;

		for (int i = 2; i * i <= n; i++) {
			if (!prime[i]) continue;

			for (int j = i * 2; j <= n; j += i)
				prime[j] = false;
		}

		for (int i = 2; i <= n; i++)
			if (prime[i])
				list.add(i);

		return list;
	}
}