백준 소수의 연속합 1644 자바

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

 

 

 

문제를 읽어보면, "소수의 연속합"으로 특정 자연수를 나타내야 한다.

예시에 나와있듯이 20은 7+13으로 나타낼 수 있지만 "연속된 소수" 들이 아니기 때문에 (7과 13 사이에는 11이 있다)

잘못된 경우이다.

 

그럼 문제를 어떻게 풀어야 할지 생각해보면

1. 소수 리스트를 구한다. 특정 값이 소수인가? 가 아닌 범위내의 모든 소수들의 값을 구하는 것이기 때문에

에라토스테네스의 체를 사용한다.  시간복잡도는  O(n * log(log n))

 

2. 소수 리스트를 구했으면, "연속된 소수" 로 나타내야 하기 때문에 투포인터로 풀이가 가능할 것 같다.

 

 

에라토스테네스의 체와 투포인터로 풀이한 코드는 아래와 같다.

 

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> primeList;

    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        prime = new boolean[N+1];
        primeList = 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]) {
                primeList.add(i);
            }
        }

        // 투포인터
        int start = 0, end = 0, sum = 0, cnt = 0;
        while (true) {
            if (sum >= N) sum -= primeList.get(start++);
            else if (end == primeList.size()) break;
            else sum += primeList.get(end++);

            if (sum == N) cnt++;
        }

        System.out.println(cnt);

    }
}