문제 바로가기

나의 풀이

소수인지 아닌지 매번 확인하면 시간초과가 반드시 날것이라 생각해서 '에라토스테네스의 체'를 활용해 list에 4백만까지의 숫자 중에서 소수만을 넣어주었다.

그 이후에는 단순히 투포인터를 활용해서 더해줬는데, 내가 실수했던 부분이 left와 right의 시작점이 둘 다 0이었어야 했는데 left = 0, right = 1부터 시작하게 해서 97%에서 자꾸 틀리는 바람에 시간이 조금 더 걸렸다.

문제를 봤을 때, 연속적인 숫자들의 합이면 누적합을 써서 right에 해당하는 누적합 - left에 해당하는 누적합 과 같이 시간 복잡도를 더 줄일 수 있다는 생각을 했다.

그러나

• 누적합 알고리즘을 구현하는데도 어느정도 시간이 소요되고
• 1부터 4백만까지의 소수의 개수도 40만개 가량밖에 되지 않으며
• 투포인터를 활용하게되면 left가 right를 넘어가는 경우 등에서 break를 사용하면 되고
• 마지막으로 2초의 시간제한 문제이므로
  단순하게 문제를 풀었다!

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

class Main {

    static boolean prime[] = new boolean[4_000_001];
    static List<Integer> prime_list = new ArrayList<>();

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

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

        prime();
        int size = prime_list.size();

        int count = 0;
        int left = 0;
        int right = 0;

        while (true) {
            int sum = sum(left, right);
            if (sum == N) {
                count += 1;
                right += 1;
            } else if (sum < N) {
                right += 1;
            } else {
                left += 1;
            }
            if (right == size || left == size || left > right) {
                break;
            }
        }

        System.out.println(count);
    }

    static void prime() {

        int n = 4000000;
        // 소수가 아니면 true
        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 = 0; i < 4000001; i++) {
            if (!prime[i]) {
                prime_list.add(i);
            }
        }
    }

    static int sum(int start, int end) {
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += prime_list.get(i);
        }
        return sum;
    }
}