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

[문제 링크] 자바 1644 소수의 연속합

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

1644번: 소수의 연속합

 

[생각 흐름]

먼저 에라토스테네스의 체를 이용하여 목표하는 값 이하까지의 소수 배열을 구한다.

이후에 투 포인터를 활용하여 만약 goal 값보다 현재값이 커지면 left를 오른쪽으로 옮기고 , goal 보다 작아지면 right를 오른쪽으로 옮겨 가면서 계산한다.(현재 sum에는 left~right까지의 배열의 합이 들어있다)

 

만약 목표값과 같으면 cnt를 하나 증가시키고 오른쪽을 증가시키도록 한다

종료시점은 right가 끝에 닿을 때까지 진행하도록 하였다.

left를 확인하지 않아도 되는이유는 if문안에서 미리 확인하고 left,right를 옮기기 때문에 right가 끝으로 옮겨지는 경우는 goal보다 현재 sum값이 작은 경우이므로 right가 범위를 벗어나면  while문을 빠져나올 수 있다.

int left = 0, right = 0;
int sum = 0;
while (right < pr.length) {
    if (pr[right] + sum > n) sum -= pr[left++];
    else if (pr[right] + sum <= n) {
        if (pr[right] + sum == n) cnt++;
        sum += pr[right++];
    }

 

[코드]

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

public class Main {

    private static void checkprime(int n) {
        boolean prime[] = new boolean[n + 1];
        prime[0] = prime[1] = true;

        for (int i = 2; i < Math.sqrt(n) + 1; i++) { //제곱근 만큼 돌아도 계산 가능
            if (prime[i]) continue;
            for (int j = i * i; j < n + 1; j += i) prime[j] = true; //에라토스테네스의 체 사용
        }
        int cnt = 0;

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

        for (int i = 1; i < n + 1; i++)
            if (!prime[i]) plist.add(i);


        Integer[] pr = plist.toArray(new Integer[0]);
        int left = 0, right = 0;
        int sum = 0;
        while (right < pr.length) {
            if (pr[right] + sum > n) sum -= pr[left++];
            else if (pr[right] + sum <= n) {
                if (pr[right] + sum == n) cnt++;
                sum += pr[right++];
            }
        }

        System.out.println(cnt);
    }


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

        int n = Integer.parseInt(br.readLine());
        checkprime(n);

    }
}