[백준] 1644번 소수의 연속합 (JAVA)

문제

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

1644번: 소수의 연속합

 

설명

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야 한다.

먼저 입력된 수보다 작거나 같은 소수를 구한다.

에라토스테네스의 체를 이용하면 쉽게 구할 수 있다.

소수인 수의 배수만 지우면 나머지는 소수가 된다는 방식이다.

나중에 연속된 소수의 합을 구하기 쉽게 소수인 수만 primeList에 저장해놓는다.

boolean[] prime = new boolean[N + 1];
List<Integer> primeList = new ArrayList<>();

// 소수는 false로 표시, 0과 1은 소수가 아니다
prime[0] = true;
prime[1] = true;

void setPrime() {
    // 에라토스테네스의 체를 이용해 소수를 구한다
    for (int i = 2; i * i <= N; i++) {
        // i가 소수라면
        if (!prime[i]) {
            // i의 배수는 모두 소수는 아니다
            for (int j = i * 2; j <= N; j += i) {
                prime[j] = true;
            }
        }
    }

    // 소수만 리스트에 옮긴다
    for (int i = 2; i <= N; i++) {
        if (!prime[i])
            primeList.add(i);
    }
}

primeList는 정렬되어 있는 리스트이므로 투 포인터를 사용해 연속적인 합을 구한다.

처음에 start 포인터와 end 포인터를 시작 위치인 0으로 설정한다.

sum과 N을 비교하면서 포인터를 각각 이동시킨다.

해당 과정에 대해 더 자세히 알고 싶으면 백준 2003번 글을 참고하자.

void findSum() {
    // primeList : 정렬되어 있는 리스트
    // 투 포인터를 사용해 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구한다
    int start = 0;
    int end = 0;
    int sum = 0;

    while (start < primeList.size()) {
        if (sum >= N || end == primeList.size()) {
            sum -= primeList.get(start++);
        }
        else {
           sum += primeList.get(end++);
        }

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

 

전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static int N;
    static boolean[] prime;
    static List<Integer> primeList;
    static int answer;

    static void setPrime() {
        // 에라토스테네스의 체를 이용해 소수를 구한다
        for (int i = 2; i * i <= N; i++) {
            // i가 소수라면
            if (!prime[i]) {
                // i의 배수는 모두 소수는 아니다
                for (int j = i * 2; j <= N; j += i) {
                    prime[j] = true;
                }
            }
        }

        // 소수만 리스트에 옮긴다
        for (int i = 2; i <= N; i++) {
            if (!prime[i])
                primeList.add(i);
        }
    }

    static void findSum() {
        // primeList : 정렬되어 있는 리스트
        // 투 포인터를 사용해 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구한다
        int start = 0;
        int end = 0;
        int sum = 0;

        while (start < primeList.size()) {
            if (sum >= N || end == primeList.size()) {
                sum -= primeList.get(start++);
            }
            else {
                sum += primeList.get(end++);
            }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        prime = new boolean[N + 1];
        primeList = new ArrayList<>();

        // 소수는 false로 표시, 0과 1은 소수가 아니다
        prime[0] = true;
        prime[1] = true;

        setPrime();

        findSum();

        System.out.println(answer);
    }
}