[백준 알고리즘] 1644번 : 소수의 연속합 (JAVA) 문제 풀이

2 초

128 MB

32096

13748

9567

41.616%

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

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

1644번: 소수의 연속합

어떻게 풀 것인가?

이 문제는 수학의 2가지 개념이 들어가있다고 생각한다.

1. 소수를 구하는 에스토라테네스의 체

2. 연속합을 물어보는 투포인터 알고리즘

이 2가지를 응용하여 풀 수 있다면 굉장히 쉬운 문제라고 생각한다.

그리하야 우선 처음에 입력받은 N만큼 에라토스테네스의 채를 이용하여 소수를 구하고

그에 따른 소수들을 전부 배열에 입력한다. 

그 이후에 부분합에 따른 합에 대한 경우의 수를 찾고, 존재하지않는다면 -1를 출력하면 된다.

시간복잡도

시간 복잡도는 처음에 에라토스테네스의 체에 따른 O(N)과 부분합에 대한 시간복잡도 O(N)만을 고려하면 된다. 그러므로 O(N)이다.

공간복잡도

소수를 담는 배열의 공간복잡도만을 고려했다. O(N)이다.

풀면서 놓쳤던점

수학적인 부분에서 부분합에 대한 것을 잘 몰라서 고려하기 어려웠다. 이번 문제를 통해서 많이 배웠던 것 같다.

이 문제를 통해 얻어갈 것

에라토스테네의 체 와 그를 활용한 투포인터 알고리즘에 대해서 공부할 수 있었다고 생각한다.

내 코드

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

// 백준알고리즘 1644번 소수의 연속합

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());
        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);
            }
        }

        int start = 0, end = 0, sum = 0, answer = 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) answer++;
        }
        System.out.println(answer);

    }
}