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

1644번 - 소수의 연속합

 

<문제>

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

1644번: 소수의 연속합

 

<문제 풀이>

먼저 N을 입력받는다.

1부터 입력받은 N까지의 범위에서 소수를 찾아 primeArr에 추가한다. 

이 문제는 소수의 합으로 N을 구하는 경우의 수 이기도 하지만, 연속된 소수의 합으로 이뤄져야 한다. 

어떤 방법을 사용해야 할지 잘 생각이 나지 않아 구글링을 해봤다.

이 과정에서 '슬라이딩 윈도우 알고리즘'을 알게 되었고, 해당 글을 참고해서 문제를 풀었다. 

연속된 소수의 합을 위해 누적된 값이 N이 넘지 않는다면 다음 인덱스의 요소를 더하고 단약 누적된 값이 N보다 크거나 같으면 시작하는 인덱스를 증가하여 누적값의 시작점을 옮긴다. 

최종적으로 누적된 값과 N의 값이 동일하면 반복문을 종료한다. 

while(true) {
	if(sum >= N) 
		sum -= primeArr.get(start++); //시작 인덱스를 증가하여 시작점을 한 칸 옮김
	else if(end == primeArr.size()) 
		break; //List의 끝에 도달하면 반복문 종료
	else 
		sum += primeArr.get(end++);
			
	if(sum == N) cnt++; //최종적으로 출력되는 값
}

 

<코드>

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

public class Main {
	static final int MAX = 4000000;
	static int N, cnt = 0;
	static int[] prime = new int[MAX+1];
	static ArrayList<Integer> primeArr = new ArrayList<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		//소수 구하기
		makePrimeArr();

		//연속합으로 정수를 구할 수 있는지 판별
		//슬라이딩 윈도우 알고리즘
		int start = 0, end = 0;
		int sum = 0, cnt = 0;
		
		while(true) {
			if(sum >= N) 
				sum -= primeArr.get(start++);
			else if(end == primeArr.size()) 
				break;
			else 
				sum += primeArr.get(end++);
			
			if(sum == N) 
				cnt++;
		}
		
		System.out.println(cnt);
	}
	
	public static void makePrimeArr() {
		for(int i = 1; i <= N; i++) {
			prime[i] = i;
		}
		
		for(int i = 2; i * i <= N; i++) {
			if(prime[i] == 0) continue;
			for(int j = i * i; j <= N; j += i) {
				prime[j] = 0;
			}
		}

		for(int i = 2; i <= N; i++) {
			if(prime[i] != 0) {
				primeArr.add(prime[i]);
			}
		}
	}
}

 

<결과>