백준 1644 자바 - 소수의 연속합 (boj 1644 java)

문제 : boj1644

 

  소수의 연속합인걸 일단 생각 안하고 그냥 어떠한 자연수로 이루어진 배열이 있고, 연속한 배열의 부분합이 N인걸 찾는다고 생각해보자. 일단 단순히 모든 범위를 보려면 O(N^2) 이므로 통과할 수 없다. 그렇다고 DP로 풀자니 식이 잘 떠오르지 않았다. 보통 이런류의 연속합은 투포인터를 활용하면 쉽게 찾을 수 있다(원래는 통과할 방법 찾기 전에 대충 어떠한 수가 소수의 연속합으로 몇 번 정도 나오는지 궁금해서 대충 짜보고 돌린건데 통과했다 ㅋㅋ).

 

  투포인터 전략만 잘 세우면 된다. st와 ed라는 두 포인터를 두고 [st, ed] 구간에 포함된 합을 계속 계산하고 있다고 해보자. 시작은 st와 ed 둘 다 배열의 첫번째에 둔다. 이 경우 ed가 증가(다음 칸으로 전진)되면 합이 늘어날 것이고, st가 증가할 경우 합이 줄어들 것이다. 그리고 이 문제는 무조건 어떠한 배열에서 연속인 구간의 합만 구하면 되므로 다음과 같이 로직을 세우면 된다.

 

A. [st, ed] 구간의 합이 N보다 크거나 같은 경우 -> ed를 증가시켜서 합을 늘리면 답을 찾을 수 없을테니 당연히 st를 증가시켜야 한다. 또한 ed가 이미 배열의 끝에 도달한 경우에도 st를 증가시켜줘야 한다.(단, ed가 배열의 끝인데 합이 N보다 작은 경우라면 종료시켜줘도 된다.)

B. [st, ed] 구간의 합이 N보다 작은 경우 -> ed를 증가시켜서 합을 늘려줘야 한다.

 

위의 두 과정을 st와 ed가 둘 다 배열의 끝에 도달할 때까지 진행하면서 A, B 이후에 합이 N인 경우를 카운팅하면 된다.

 

  그리고 맨 처음에 말한 '어떠한 배열' 부분에 에라토스테네스의 체 등을 활용해 소수를 구해 넣어주면 될 것이다. 즉, 굳이 소수가 아니라도 위의 방법으로 가능하다.

 

  예를들어 N=17인 경우 위 로직에 따른 전체 과정은 다음과 같다.

 

 

코드 : github

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

public class Main {
    ArrayList<Integer> pn = new ArrayList<>();

    private void initPn(int n) {
        boolean[] isPn = new boolean[n+1];
        int sqrtN = (int)Math.sqrt(n);
        for (int i = 3; i <= sqrtN; i+=2) {
            if (isPn[i]) continue;
            int base = i+i;
            while (base <= n) {
                isPn[base] = true;
                base+=i;
            }
        }
        pn.add(2);
        for (int i = 3; i <= n; i+=2) {
            if (!isPn[i]) pn.add(i);
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        initPn(n);
        int st = -1;
        int ed = -1;
        int sum = 0;
        int cnt = 0;
        while (st != pn.size()-1 || ed != pn.size()-1) {
            if (sum < n && ed != pn.size()-1)
                sum += pn.get(++ed);
            else
                sum-=pn.get(++st);

            if (sum == n) cnt++;
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}