자바 백준 1644번 문제 - 소수의 연속합

문제출처 : https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

문제 :

 

 

소스코드 :

import java.util.*;
class Main {
	// 소수를 구해서 소수 배열을 만드는 함수 작성
	// 에라토스테네스 체 알고리즘 적용
	public ArrayList<Integer> primeArr(int n) {
		ArrayList<Integer> arr = new ArrayList<>();
		boolean[] p = new boolean[n+1];
		Arrays.fill(p, true);
		p[0] = p[1] = false;
		for(int i=2; i*i<=n; i++) {
			if(p[i]) {
				for(int j=i*i; j<=n; j+=i) {
					p[j] = false;
				}
			}
		}
		for(int i=0; i<n+1; i++) {
			if (p[i] == true) arr.add(i);
		}
		return arr;
	}

	// 소수 배열에서 연속된 소수 합으로 나타낼 수 있는 경우의 수 구하기
	// 투포인터 알고리즘과 슬라이딩 윈도우 알고리즘 적용
	public int solution(int n) {
		int answer = 0;
		ArrayList<Integer> pArr = primeArr(n);
		int lt = 0, sum = 0;
		for(int rt=0; rt<pArr.size(); rt++) {
			sum += pArr.get(rt);
			while (sum > n) {
				sum -= pArr.get(lt++);
			}
			if (sum == n) answer++;
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println(T.solution(n));
	}
}

 

풀이 :

소수 배열을 구하는 함수에는 에라토스테네스 체 알고리즘을 적용하고

소수 배열에서 연속된 소수 합으로 나타낼 수 있는 경우의 수를 구하는 함수에서는

투포인터 알고리즘 + 슬라이딩 윈도우 알고리즘을 적용해

시간복잡도를 최소화하여 풀었다.

내가 배운 알고리즘을 그대로 적용하면 풀리는 문제였기 때문에 상당히 쉽게 풀었다.