1644번 소수의 연속합 - node.js
해당 포스팅은 백준 1644번 소수의 연속합 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
문제
문제 설명
자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하자.
-
가능한 케이스
3
: 3 (한 가지)41
: 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)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. 로직
sum < n
right를 1 증가시켜 sum의 값을 늘린다.sum === n
- 연속된 부분합이므로 answer += 1
- 그 다음 부분합을 구하기 위해 left를 1 증가시켜준다.
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);
Author And Source
이 문제에 관하여(1644번 소수의 연속합 - node.js), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dev-redo/백준-1644번-소수의-연속합-node.js저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)