[백준 1644] 소수의 연속합

문제         

레벨:  G3
알고리즘: 투 포인터 +  에스토라테네스의 체
풀이시간: 1시간
힌트 참조 유무: 유

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

1 번째 시도 : 시간초과  

[코드 설명]

1. arr배열에 N이하의 소수들을 담는다.
2. 소수들을 순회하며 while문 안의 내용을 반복한다.

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

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());
        int count = 0;

        int start = 0;
        int end = 0;
        int now = 1;
        int sum = 0;
        int input = 0;

        int[] arr = new int[N + 1];

        if (isSosu(N))
            count++;
        int a = 0;
        for (int i = 1; i <= N; i++) {
            if (isSosu(i)) {
                arr[a] = i;
                a++;
            }
        }

//        for (int i =0; i < N; i++) {
//            System.out.println(arr[i]);
//        }


        while (arr[start] < (N / 2 + 1)) {
            if (sum <= N) {
                sum += arr[end];
                end++;
            } else if (sum > N) {
                sum -= arr[start];
                start++;
            }

            if (sum == N) {
                count++;
            }
//
//            System.out.println(start);
//            System.out.println(end);
//            System.out.println(arr[start]);
//            System.out.println(arr[end]);
//            System.out.println(sum);
//            System.out.println(count);
//            System.out.println();
        }

        System.out.println(count);
    }

    public static boolean isSosu(int n) {
        if (n == 1) {
            return false;
        }

        int count = 0;
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                count++;
            }
        }

        if (count == 1)
            return true;
        else {
            return false;
        }
    }
}

 

2 번째 시도: 성공  

[놓쳤던 개념]

 에스토라테네스의 체

 

[부족한 개념]

투 포인터 종료조건 

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

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());
        int count = 0;

        int start = 0;
        int end = 0;
        int sum = 0;

        boolean[] prime = new boolean[N + 1];
        ArrayList<Integer> primeNumbers = new ArrayList<>();

        // 소수 판별을 위한 에라토스테네스의 체
        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 = 2; i <= N; i++) {
            if (!prime[i]) {
                primeNumbers.add(i);
            }
        }

        // 소수의 연속합을 찾기 위한 투 포인터 알고리즘
        while (true) {
            if (sum >= N) {
                sum -= primeNumbers.get(start++);
            } else if (end == primeNumbers.size()) {
                break;
            } else {
                sum += primeNumbers.get(end++);
            }

            if (sum == N) {
                count++;
            }
        }

        System.out.println(count);
    }
}