[백준 JAVA] 1644 : 소수의 연속합

[백준 1644] 소수의 연속합 : https://www.acmicpc.net/problem/1644

---

문제 조건 정리

 

1. 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
   • 3 : 3 (한 가지)
   • 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
   • 53 : 5+7+11+13+17 = 53 (두 가지)
   
   
2. 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다.
   7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다.
   또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.
   
   
3. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

---

입력

 

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

---

문제를 풀기 전

 

1. N까지의 소수를 리스트에 저장해야겠다.
   
   
2. 이를 위해 에라토스테네스의 채 알고리즘을 한번 더 확인했다. 떠오르지만 생각이 나지 않는..
   
   
3. 소수 리스트를 읽는 포인터를 두 개를 두고
   1번 포인터를 start (초기값 = 0),
   2번 포인터를 end (초기값 = 0),
   
   start에서 end까지의 연속합 sum (초기값 = 0)을 구해서
   
   목표하는 값(N)보다 작다면 : sum += primes[end++]
   목표하는 값(N)보다 크다면 : sum -= primes[start++]
   목표하는 값(N)과 동일하면 : sum += primes[end++], count++
   
4. 정답은 count

 

---

코드

 

package baekJoon;

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

public class BJ1644 {

    static List<Integer> primes = new ArrayList<>();
    static int n;
    static int count = 0;

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());

        // true : 소수가 아님
        // false : 소수 (기본값)
        boolean[] isntPrime = new boolean[n + 1];

        // 0, 1은 소수가 아님
        isntPrime[0] = isntPrime[1] = true;

        // i를 2부터 √n까지 반복
        for (int i = 2; i * i <= n; i++) {
            // i가 소수(혹은 기본값)라면
            if (!isntPrime[i]) {
                // i의 배수는 모두 소수가 아니다
                // j를 i*i부터 시작하여 i씩 증가시키며 소수가 아니라고 표시
                for (int j = i * i; j <= n; j += i) {
                    isntPrime[j] = true;
                }
            }
        }

        // 2는 소수다.
        primes.add(2);
        
        // 3부터 홀수를 체크하며 소수 리스트를 채운다
        // 간단히 연속합을 구하기 위해서
        for (int i = 3; i <= n; i += 2) {
            if (!isntPrime[i]) {
                primes.add(i);
            }
        }

//        for (int prime : primes) {
//            System.out.println(prime);
//        }
        
        // 0(start)번째 소수부터 0(end)번째 소수까지 더한다.
        calcContinuousSum(0, 0);

        System.out.println(count);

    }

    private static void calcContinuousSum(int start, int end) {
        int sum = 0;

//        System.out.println("primes = " + primes.size());

        // end 가 소수 리스트의 끝을 넘어서지 않았다면
        while (end < primes.size()) {

            // 소수의 연속합이 목표보다 작다면
            // 연속합에 end를 더하고 end++
            if (sum < n) {
                sum += primes.get(end++);
                continue;
            }
            // 소수의 연속합이 목표보다 크다면
            // 연속합에 start를 뺴고 start++
            if (sum > n) {
                sum -= primes.get(start++);
                continue;
            }
            // 소수의 연속합이 목표와 같다면
            // 연속합에 end를 더하고 end++ (다음 연속합도 구하기 위해서)
            // count(정답)++
            if (sum == n) {
                count++;
                sum += primes.get(end++);
                continue;
            }
        }

        // 위 반복을 완료한다면 
        // 소수 리스트의 마지막과 목표값이 같은지 비교
        // end++를 해서 마지막 while문의 조건에 만족하지 못해서 예외처리..
        if (n == primes.get(primes.size() - 1)) {
            count++;
        }
    }
}

 

---

문제를 풀고 난 후

 

start ~ end 까지의 연속합을 구하는 과정에서 항상 start ~ end 의 값을 for 문으로 반복하며 더하려고 하니 시간이 오래 걸려서 아이디어를 생각해내고 기발하다고 생각했는데, 다른 풀이를 보니 거의 비슷해서 역시 나는 기발하지 못했다. 그래도 올바르게 풀어서 다행이다

 

에라토스테네스의 채는 항상 헷갈리는 것 같다. 반복을 진행하며 올바르게 진행되는 알고리즘이 직관적으로 와닿지 못해서 그런 것 같다.