[Java] 백준 1644번 : 소수의 연속합

1. 문제

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

1644번: 소수의 연속합

 

 

 

2. 풀이 과정

소수 구하기는 에라토스테네스의 체를 사용했고, 연속된 수의 합은 dp를 활용했다.

2부터 N까지 보면서, 소수가 보이면 values배열에 더한 값을 저장한다.

 

예시로 N=15일 때를 생각해보면, 

i=2

values = [2]

i=3

values = [5, 3]

i=4

values = [9, 7, 4]

i=5

values = [14, 12, 9, 5]

i=6

values = [20, 18, 15, 11, 6]  => result++;

...

 

15보다 큰 값은 N(15)가 될 가능성이 없으므로, 다음부터 보지 않도록 start, end로 범위를 한정해준다.

i=6일 때, start = 4이고 end = 1이 되며, 15, 11, 6에 다음 소수를 더해줄 것이다.

 

import java.io.*;

public class Boj1644 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		boolean notPrime[] = new boolean[N+1];//false는 소수
		int limit = (int)Math.sqrt(N);
		notPrime[0] = notPrime[1] = true;
		int values[] = new int[N+1], start = -1, end=-1, result=0;
		//에라토스테네스의 체
		for(int i=2; i<=N; i++) {
			if(notPrime[i]) {continue;}
			if(i<=limit) {
				for(int j=i+i; j<=N; j+=i) {notPrime[j]=true;}
			}
			for(int j=start; j>end; j--) {
				values[j]+=i;
				if(values[j]>N) {
					end=j;
					break;
				}
				if(values[j]==N){result++;}
			}
			if(i==N){result++;}
			values[++start]=i;
		}
		System.out.println(result);
	}
}