[ 백준 ] 1644 소수의 연속합

Link | 백준 1644번 문제 : 소수의 연속합

📌 About

이번 문제는 소수 찾기와 two pointer로 해결할 수 있다.

📌 Solution

우선 NUM이 주어졌을 때 NUM까지의 소수 여부를 판단해야 한다.

소수 판단은 에라토스테네스의 체로 해결할 수 있다.

boolean[] isNotPrime = new boolean[NUM + 1];
for (int n = 2; n <= NUM; n++)
    if (!isNotPrime[n])
        for (int ne = n + n; ne <= NUM; ne += n) isNotPrime[ne] = true;

Stream filter를 사용하여 prime number 만으로 이루어진 배열을 만들 수 있다.

int[] primes = IntStream.rangeClosed(2, NUM).filter(num -> !isNotPrime[num]).toArray();

에라토스테네스의 체와 prime 추출을 다음과 같이 한 번에 할 수 있다.

int[] primes = IntStream.rangeClosed(2, NUM).filter(num -> {
    if (!isNotPrime[num])
        for (int n = num + num; n <= NUM; n += num)
            isNotPrime[n] = true;
    return !isNotPrime[num];
}).toArray();

이후에는 two pointer로 앞에서부터 탐색한다.

int front = 0, back = 1, sum = primes[0], count = 0;
while (true) {
    if (sum >= NUM) {
        if (sum == NUM) count++;
        if (front + 1 == back) break;
        sum -= primes[front++];
    } else {
        if (back == primes.length) break;
        sum += primes[back++];
    }
}

front는 현재 합산 범위의 첫 원소 위치이다.

back은 현재 합산 범위의 마지막 원소 위치 + 1이다.

sum은 현재 합산값이다.

count는 NUM이 될 수 있는 합산 개수이다.

만약 합산값이 NUM보다 크면 가장 작은 소수를 감산한다.

다만, 더는 감산할 값이 없으면 탐색을 종료한다.

만약 합산값이 NUM과 같으면 count를 1 가산하고 위와 동일한 연산을 한다.

만약 합산값이 NUM보다 크면 합산 범위 이후 첫 소수를 가산한다.

다만, 더는 가산할 값이 없으면 탐색을 종료한다.

📌 Code

GitHub Repository

public void solve() throws IOException {
    final int NUM = Integer.parseInt(reader.readLine());
    if (NUM == 1) result.append(0);
    else {
        boolean[] isNotPrime = new boolean[NUM + 1];
        int[] primes = IntStream.rangeClosed(2, NUM).filter(num -> {
            if (!isNotPrime[num])
                for (int n = num + num; n <= NUM; n += num)
                    isNotPrime[n] = true;
            return !isNotPrime[num];
        }).toArray();
        int front = 0, back = 1, sum = primes[0], count = 0;
        while (true) {
            if (sum >= NUM) {
                if (sum == NUM) count++;
                if (front + 1 == back) break;
                sum -= primes[front++];
            } else {
                if (back == primes.length) break;
                sum += primes[back++];
            }
        }
        result.append(count);
    }
}