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

백준 1644 문제 정리 글입니다.

(최적화된 답은 아니니 참고만 하시기 바랍니다.)

 

백준 1644문제 소수의 연속함 

해당 문제를 풀기 위해서는 두개 단계를 고려 해야 한다.

 

1. 소수 구하기.

2. 소수의 연속 합으로 주어진 정수를 구할 수 있는지 판단하기.

 

1. 소수 구하기

 

소수를 구하기 위해서는 에라토스테네스의 체를 이용하면 된다.

자세한 알고리즘은 아래 글에서 확인

 

https://firework-ham.tistory.com/8

[JAVA] 소수 구하는 알고리즘 : 에라토스테네스의 체

소수를 구하기 위해 아래와 같이 선언하여 주어진 N 사이에 소수를 구한다.

 

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

public class Main {

	static boolean prime[];
	static ArrayList<Integer> prime_numbers = new ArrayList<>();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
   
   		// 1. 소수 구하기
        prime = new boolean[N+1];        
        prime[0] = prime[1] = true;       
        for(int i=2; i*i<=N; i++){
            if(!prime[i]) for(int j=i*i; j<=N; j+=i) prime[j]=true;                
        }            
        for(int i=1; i<=N;i++){
        	if(!prime[i]) prime_numbers.add(i);     
        }
        
        // 2. 연속합으로 주어진 정수 구할 수 있는지 판별
	}	
}

 

2. 연속합으로 주어진 정수 구할 수 있는지 판별

 

연속합으로 주어진 정수를 구할 수 있는지 판별하는 방법은 슬라이딩 윈도우 알고리즘으로 확인하면 된다.

에라토스테네스의 체를 이용해 구한 소수를 가지고 연속합을 만들면서 합이 크면 시작 Index를 늘리고 합이 작으면 끝 Index를 늘리는 방식으로 구한다.

 

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

public class Main {

	static boolean prime[];
	static ArrayList<Integer> prime_numbers = new ArrayList<>();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
   
   		// 1. 소수 구하기
        prime = new boolean[N+1];        
        prime[0] = prime[1] = true;       
        for(int i=2; i*i<=N; i++){
            if(!prime[i]) for(int j=i*i; j<=N; j+=i) prime[j]=true;                
        }            
        for(int i=1; i<=N;i++){
        	if(!prime[i]) prime_numbers.add(i);     
        }
        
        // 2. 연속합으로 주어진 정수 구할 수 있는지 판별
        int start=0, end=0, sum=0, count=0;
        while(true) {
        	if(sum >= N ) sum -= prime_numbers.get(start++);
        	else if(end == prime_numbers.size()) break;
        	else sum += prime_numbers.get(end++);       	
        	if(N==sum) count++;        	
        }		
        System.out.println(count);	
    }	
}