BOJ - 1644 ) 소수의 연속합

---

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

1644번: 소수의 연속합

 

---

투포인터를 이용해 연속한 소수의 합으로 목표숫자를 만들수 있는지? 없는지 확인하는 문제이다.

 

만들어야하는 숫자를 N이라고 할때에, N이하의 연속된 소수들의 배열이 필요하다.

 

몇개가될지모르기에 ArrayList에 하나하나 확인하면서 배열을 만들었다. O ( N*logN)

 

그 이후 처음부터 e가 끝까지 갈때까지 O ( N )만큼 진행하면서 조건에 맞는지 확인한다.

 

연속합이 N보다 큰경우, S쪽에서 하나빼주고 N보다 작으면 더 늘려야하기때문에 

 

E쪽에서 하나더해준다. O ( 2*N ) 

 

총 O ( N*logN + 2*N ) 으로 해결가능!

 

---

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

public class 소수의연속합 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		if(n==1) System.out.println(0);
		else {
			ArrayList<Integer> al = new ArrayList<>();
			for(int i = 2 ; i <= n ; i++) {
				boolean isPrime = true;
				for(int j =2 ; j <= Math.sqrt(i) ; j++) {
					if(i%j ==0) {
						isPrime = false;
						break;
					}
				}
				if(isPrime) {
					al.add(i);
				} 
			}
			int sum = al.get(0);
			int res =0;
			int size = al.size();
			for(int s =0 , e =0 ; ;) {
				if(sum > n) {
					sum -= al.get(s);
					s++;
				} else if(sum < n) {
					e++;
					if(e ==size) break;
					sum +=al.get(e);
				} else {
					res++; e++;
					if(e ==size) break;
					sum +=al.get(e);
				}
			} System.out.println(res);
		
		}
	}
}

---

소수를 다룰때에 1이 포함되는지 확인해주자