[백준] 1644 소수의 연속합 - 자바

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

1644번: 소수의 연속합

문제 풀이

먼저 이 문제를 풀기 위해선 특정 범위에 해당하는 소수 리스트를 뽑아낼 줄 알아야 한다. 에라토스테네스의 체 알고리즘을 사용하여 효율적으로 특정 범위의 소수를 구할 수 있다. 

N까지의 소수를 구했다면 투 포인터(start, end)를 활용하여 합이 N인 부분의 갯수(cnt)를 찾아내면 된다. 투 포인터 활용은 간단하다.

1. 부분 합이 크다면 -> start를 증가시켜 부분합을 감소시킨다
2. 부분 합이 작다면 -> end를 증가시켜 부분합을 증가시킨다
3. 부분 합이 같다면 -> cnt를 증가시키고 또 다른 부분합을 찾기 위해 (1) or (2)를 수행한다.

while (start <= end && end < primes.length) {
    if (partialSum == N) {
        cnt++;
        partialSum -= primes[start]; // 다른 값을 또 찾기 위해
        start++;
    }
    if (partialSum < N) {
        partialSum += primes[end];
        end++;
    }
    if (partialSum > N) {
        partialSum -= primes[start];
        start++;
    }
}

while (start <= end)

start가 end보다 커진다는 얘기는 start=end일 때 partialSum>=N이었다는 얘기다. 그 말은 start와 end가 가리키는 값이 N보다 크므로 그 이후로는 N을 만족하는 숫자가 나올 수 없다. 왜? 그 이후의 값들은 모두 N보다 크니까..

 

while (end < primes.length)

어떻게 보면 당연한 얘기다. 하지만 이 로직에는 한 가지 문제점이 있다. 찾으려고 하는 부분합이 맨 마지막 인덱스(last라고 하자)를 포함한다고 할 때 end는 last를 포함하고 end++을 통해 primes.length를 벗어나게 되어 while문을 벗어난다. 따라서 그 이후 부분합을 찾지 못한다. 이해가 안 간다면 좀 더 자세히 설명 해놓은 이 글을 참고하자.

따라서 소수를 모아둔 primes 마지막에 0을 추가로 넣어주어 마지막 인덱스를 활용할 수 있도록 해주어야 한다.

0은 부분합에 영향을 주지 않기 때문에 결과에도 영향을 미치지 않는다.

primes.add(0); // 투포인터 계산을 위해 마지막에 0을 추가

 

에라토스테네스의 체

에라토스테네스의 체를 통해 소수를 구하는 로직은 따로 포스팅을 진행하도록 하겠다. 여기서는 참고만 하자.

// 에라토스테네스의 체
static int[] getPrime(int n) {
    List<Integer> primes = new ArrayList<>();
    int temp[] = new int[n+1];
    int rootN = (int)Math.sqrt(n);

    // 연속적인 숫자로 초기화
    for(int i=2; i<=n; i++) {
        temp[i] = i;
    }
    // prime이 아닌 숫자 제거
    for(int i=2; i<=rootN; i++) {
        if(temp[i] != 0 ) {
            for(int j=i+i; j<=n; j+=i) {
                temp[j] = 0;
            }
        }
    }
    // 소수인 값만 따로 저장
    for(int i=2; i<=n; i++) {
        if(temp[i] != 0) {
            primes.add(temp[i]);
        }
    }
    primes.add(0); // 투포인터 계산을 위해 마지막에 0을 추가
    return primes.stream().mapToInt(Integer::intValue).toArray();
}

 

코드

package 백준;


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

public class b1644 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] primes = getPrime(N);

        int start = 0, end = 0;
        int partialSum = 0;
        int cnt = 0;

        while (start <= end && end < primes.length) {
            if (partialSum == N) {
                cnt++;
                partialSum -= primes[start]; // 다른 값을 또 찾기 위해
                start++;
            }
            if (partialSum < N) {
                partialSum += primes[end];
                end++;
            }
            if (partialSum > N) {
                partialSum -= primes[start];
                start++;
            }
        }

        System.out.println(cnt);
    }

    // 에라토스테네스의 체
    static int[] getPrime(int n) {
        List<Integer> primes = new ArrayList<>();
        int temp[] = new int[n+1];
        int rootN = (int)Math.sqrt(n);

        // 연속적인 숫자로 초기화
        for(int i=2; i<=n; i++) {
            temp[i] = i;
        }
        // prime이 아닌 숫자 제거
        for(int i=2; i<=rootN; i++) {
            if(temp[i] != 0 ) {
                for(int j=i+i; j<=n; j+=i) {
                    temp[j] = 0;
                }
            }
        }
        // 소수인 값만 따로 저장
        for(int i=2; i<=n; i++) {
            if(temp[i] != 0) {
                primes.add(temp[i]);
            }
        }
        primes.add(0); // 투포인터 계산을 위해 마지막에 0을 추가
        return primes.stream().mapToInt(Integer::intValue).toArray();
    }

}

 

느낀점

특정 범위의 소수를 구하는 로직이 막혀서 추가로 공부를 하게 되었는데 알아두면 유용하게 쓰일 것 같다.