[백준(Baekjoon)][자바(java)] 1644 : 소수의 연속합 / 두 포인터

 

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

문제 풀이

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()), i, j;
		br.close();

		boolean b[] = new boolean[n + 1];
		for (i = 2; (i * i) <= n; i++)
			if (!b[i])
				for (j = i * 2; j <= n; j += i)
					b[j] = true;

		List<Integer> a = new ArrayList<>();
		for (i = 2; i <= n; i++)
			if (!b[i])
				a.add(i);
		
		int left = 0, right = 0, sum = 0, cnt = 0, size = a.size();
		while (true) {
			if (sum >= n) {
				if (sum == n) 	cnt++;
				sum -= a.get(left++);
			} else {
				if (right == size) break;
				sum += a.get(right++);
			}
		}
		
		System.out.println(cnt);
		
	}

}

 

*  두 포인터

-  '에라토스테네스의 체'를 이용하여 1부터 n까지의 수들 중 소수를 구해 리스트 a에 담는다

-  리스트 a를 탐색하며 부분합을 구해 n이 되는 횟수를 구함

 

※ 에라토스테네스의 체 : https://hyunjiishailey.tistory.com/497

※ 부분합 : hyunjiishailey.tistory.com/261