[알고리즘] 백준 1644번 : 소수의 연속합

문제

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

 

 

 

 

📌 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
class Main {	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
        
		// 1 ~ n까지의 소수 배열
		List<Integer> pl = primeList(N);
		
		// 소수 배열 크기
		int size = pl.size();
		
		// 연속된 소수의 합 경우의 수
		int count = 0;
		
		// 연속된 소수의 합
		int sum = 0;
		int start = 0;  // 시작 지점
		int end = 0;  // 끝 지점
		
		// 투포인터 알고리즘
		while(true) {
			// 연속된 소수의 합이 N일때
			if(sum==N) {
				count++; // 경우의 수 1 추가
			}		
			
			// 연속된 소수의 합이 N보다 클 때
			if(sum>=N) {
				// sum에서 시작점 값을 빼고 시작점 한 칸 앞으로 이동
				sum-=pl.get(start++);
				continue;
			}
			
			// 끝 지점이 배열 끝일 경우 break
			if(end==size) break;
			
			// 연속된 소수의 합이 N보다 작을 때
			if(sum<N) {
				// sum에서 끝 지점 값을 더하고 끝 지점 한 칸 앞으로 이동
				sum+=pl.get(end++);
			}
		}
		
		System.out.println(count);
		
	}
	
	public static List primeList(int N) {
		
		// 1 ~ n까지 값을 넣을 배열 생성
		int[] arr = new int[N+1];
		
		// 배열 인덱스에 인덱스값 할당 
		for(int i=0; i<=N; i++) {
			arr[i] = i;
		}
		
		// 소수가 아닐 경우 배열의 요소 값을 0으로 할 것이다
		arr[1] = 0;
		
		List<Integer> li = new ArrayList<>();
		
		for(int i=1; i<=N; i++) {
			if(arr[i]==0) { // 소수가 아닐 경우
				continue;
			}
			
			// 배수를 활용하여 소수가 아닌 수를 0으로 할당
			for(int k=2; k<=N/i; k++) { // 본인은 제외하기 위해 k는 2부터 시작
				arr[i*k] = 0;
			}
			li.add(i);
		}

		return li;
	}
	
}