[백준] 1644번. 소수의 연속합(JAVA)

문제

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

---

풀이

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

public class Main {


    static int n;
    static boolean[] isPrime;
    static ArrayList<Integer> primeList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        isPrime_fun(n);
        int start = 0, end = 0, sum = 0, answer = 0;
        for(int i = 0; i < isPrime.length; i++){
            if(isPrime[i]){
                primeList.add(i);
            }
        }

        while(true){
            if(sum >= n){ // 원하는 값보다 커지는 경우에 대한 처리
                sum -= primeList.get(start++); // 제일 앞의 인덱스에 대한 값 감소 후 인덱스 증가
            }else if(end == primeList.size()){ // 만약 더 이상 더할 것은 없는데, sum 마저 n보다 크거나 같지 못하다면 종료
                break;
            }else{
                sum += primeList.get(end++); // 원하는 값보다 작다면 제일 끝의 인덱스에 대한 값 증가 후 인덱스 증가
            }
            if(sum == n){
                answer++; // 동일하다면 정답 + 1
            }
        }

        System.out.println(answer);

    }

    static void isPrime_fun(int n){
        isPrime = new boolean[n+1]; // N번째의 수 까지 받기위해 N+1까지 동적할당

        for(int i = 0; i < isPrime.length; i++){
            isPrime[i] = true; // boolean배열의 default값은 false이므로 true로 바꿔주기
        }

        isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아니니깐 false
//        System.out.println(n);

        for(int i = 2; i <= Math.sqrt(n); i++){ // 2부터 n의 제곱근까지의 모든 수를 확인
            if(isPrime[i]){ // 해당수가 소수라면, 해당수를 제외한 배수들을 모두 false 처리하기
                for(int j = i*i; j<= n; j += i){//그 이하의 수는 모두 검사했으므로 i*i부터 시작
                    isPrime[j] = false;
                }
            }
        }
    } // isPrime_fun 함수 종료

}

 

문제 난이도가 어렵다기보다는 적절한 두가지의 알고리즘을 얼마나 잘 사용할 수 있냐라는 것이 중요한 것 같다.

사용한 알고리즘은 1. 에라토스테네스의 채로 연속된 소수의 리스트를 먼저 구한 뒤, 2. 투포인터 알고리즘으로 정답을 효율적으로 찾는 것이다.