[알고리즘 / 백준] 1644 - 소수의 연속합

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

문제는 위와 같으며, 먼저 주어진 자연수보다 작거나 같은 소수를 모두 구해 배열로 저장한 뒤, low와 high 두개의 포인트를 만들어 앞에서부터 합을 구하면서 합이 n과 같아질 때 결과값을 하나 증가시키는 방식으로 문제를 해결하였습니다.

 

예제로 주어진 41을 기준으로 살펴보겠습니다. 41보다 작거나 같은 소수를 먼저 구해 배열로 저장합니다.

 

그런 다음, sum이 주어진 41보다 작은 경우 high를 한칸 뒤로 이동시키고 그 값을 sum에 추가해줍니다.

 

이렇게 같은 과정을 반복하다가 sum이 41과 같아진 경우, result의 값을 하나 증가시키고 high 위치를 한칸 뒤로 이동시킨 뒤, 그 값을 sum에 추가해줍니다.

sum이 주어진 41과 같아진 경우

result를 하나 추가시키고 high 위치를 한칸 이동 후 그 값을 sum에 추가

 

sum이 41보다 커진 경우에는 low가 가리키는 값을 sum에서 빼고 low의 위치를 한칸 뒤로 이동시킵니다.

 

low가 high보다 작거나 같고 high가 소수 배열의 길이 - 1보다 작을 때까지 위 비교를 반복 수행합니다.

low가 가리키는 값이 11, high가 가리키는 값이 17일 때, sum이 41이 되므로 result를 하나 증가시키고 high 위치를 한칸 이동시켜 그 값을 sum에 추가

 

이렇게 반복하게 되면 high가 소수의 마지막 위치까지 간 경우를 확인하지 못하기 때문에 마지막으로 소수 배열의 마지막 수가 주어진 n과 같은 경우는 result를 1증가시켜주고 최종적으로 result를 출력하면 됩니다.

 

---

 

자바 코드는 다음과 같습니다.

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

public class Main {
    private static int[] primeNum;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        findPrimeNum(n);  // 소수 찾기

        int low = 0, high = 0;
        int sum = primeNum[0];
        int result = 0;

        // 포인터를 이동시키며 소수 배열 탐색
        while (low <= high && high < primeNum.length - 1) {
            if (sum < n) {  // sum이 n보다 작은 경우
                sum += primeNum[++high];  // high를 한칸 뒤로 이동시키고 그 값을 sum에 추가
            } else if (sum == n) {  // sum이 n과 같은 경우
                result += 1;  // 결과를 하나 증가시키고
                sum += primeNum[++high];  // high를 한칸 뒤로 이동시키고 그 값을 sum에 추가
            } else if (sum > n) {  // sum이 n보다 큰 경우
                sum -= primeNum[low++];  // low가 가리키는 값을 sum에서 빼고 low의 위치를 한칸 이동
            }
        }

        // 구해진 소수의 마지막 수가 n과 같은 경우 result + 1 해주기
        if (primeNum[primeNum.length - 1] == n) {
            result += 1;
        }

        System.out.println(result);
    }

    // 주어진 수보다 작거나 같은 소수 모두 찾기
    private static void findPrimeNum(int n) {
        boolean[] isPrimeNum = new boolean[n + 1];
        Arrays.fill(isPrimeNum, true);

        ArrayList<Integer> primeNumList = new ArrayList<>();

        for (int i = 2; i < n + 1; i++) {
            if (isPrimeNum[i]) {  // 해당 인덱스가 소수인 경우
                int j = 2;
                while (i * j < n + 1) {  // 해당 인덱스의 배수를 모두 소수가 아니도록 처리
                    isPrimeNum[i * j] = false;
                    j += 1;
                }
                primeNumList.add(i);  // 해당 인덱스는 소수이므로 추가
            }
        }

        primeNum = primeNumList.stream().mapToInt(i -> i).toArray();
        // 소수가 없는 경우 임의로 0을 저장하여 반환
        if (primeNum.length == 0) {
            primeNum = new int[1];
        }
    }
}