[백준] 1644 - 소수의 연속합

[문제링크]

1644번: 소수의 연속합

 

0. 소수 구하기 + 연속합 문제

 

1. 소수 구하기 : 에라토스테네스의 체로 구하면서, 투포인터 사용시 편리하도록 ArrayList에 저장하였다

 

2. 누적합 구하기

  - N보다 같거나 커질때까지 더하며 진행

  - N보다 같거나 작아질때까지 빼며 진행

  - 원소가 하나만 남을 경우 2번 카운트되는 문제가 있어 prevFst를 두어 방지하였다

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());

		boolean[]noPrime=new boolean[N+1];
		noPrime[0]=noPrime[1]=true;
		
		ArrayList<Integer>prime = new ArrayList<>();
		for (int i = 2; i < N+1; i++) {
			if(!noPrime[i]) {
				prime.add(i);
				for (int j = i; j < N+1; j+=i) {
					noPrime[j]=true;
				}
			}
		}
		
		int count=0;
		//두포인터
		int fst=0,end=0;
		long sum=0;
		while(fst<prime.size() && end<prime.size()) {
			while(sum<N && end<prime.size()) {
				sum+=prime.get(end++);
			}
			if(sum==N) {
				count++;
				if(end<prime.size())sum+=prime.get(end++);
			}
			
			int prevFst=fst;
			
			while(sum>N && fst<prime.size()) {
				sum-=prime.get(fst++);
			}
			if(prevFst!=fst && sum==N) {
				count++;
				if(fst<prime.size())sum-=prime.get(fst++);
			}
		}
		System.out.println(count);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면