백준 1644번 소수의 연속합 - node.js

해당 포스팅은 백준 1644번 소수의 연속합 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

문제

문제 설명

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하자.

• 가능한 케이스

  1. 3 : 3 (한 가지)
  2. 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
  3. 53 : 5+7+11+13+17 = 53 (두 가지)

• 불가능한 케이스 (경우의 수 0)
  - 20:

  • 7+13 (7과 13이 불연속하므로 X)
  • 3+5+5+7 (한 소수는 반드시 한 번만 덧셈에 사용할 수 있으므로 X)

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

풀이

1. 점화식

해당 문제는 n이하의 소수를 구한다음 투포인터를 통해 n의 연속된 부분합을 구하는 문제이다.

해당 부분합을 구하기 위해서는 투포인터를 이용해야 하며, 부분합에 대한 점화식은 아래와 같다.

S[n] = 2 + 3 + ... n일 시, sum = S[right] - S[left]

2. 로직

1. sum < n right를 1 증가시켜 sum의 값을 늘린다.
2. sum === n
   • 연속된 부분합이므로 answer += 1
   • 그 다음 부분합을 구하기 위해 left를 1 증가시켜준다.
3. sum > n
   • 부분합이 n보다 크므로 left를 1 증가시켜 sum을 줄여준다.

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString();
const target = Number(input);

// 소수 배열 만들기
const isPrime = makePrime(target);
const primeArr = [];

for (let i = 2; i <= isPrime.length; i++) {
    if (isPrime[i]) primeArr.push(i)
}

function makePrime(n) {
    const numArr = new Array(n+1).fill(true);
    for (let i = 2; i <= n; i++) {
        if (numArr[i] === 0) continue;
        for (let j = i ** 2; j <= n; j += i) {
            numArr[j] = false;
        }
    }
    return numArr;
}

// 경우의 수 구하기
let [left, right] = [0,0];
let sum = 0;
let answer = 0;

while (left <= right) {
    if (sum < target) {
        sum += primeArr[right++];
        continue;
    }
    if (sum === target) answer++;
    sum -= primeArr[left++];
}

console.log(answer);