[백준 알고리즘] 1208번 부분수열의 합 2 node.js JavaScript JS

1208번: 부분수열의 합 2

😉문제 풀이 설명

문제에서 주어진 숫자는 최대 40개. 40개로 부분 수열을 만든다면 경우의 수가 2^40으로 시간초과가 됩니다. 따라서 다음과 같은 전략으로 문제를 풀 수 있습니다.

두 배열을 나누어서 경우의 수를 구합니다. 배열을 두 개로 나누면, 경우의 수가 2^20을 가진 배열 2개를 가지게 됩니다. 2^20은 100만번의 순회가 이루어져 시간 제한을 넘기지 않습니다. 따라서 두 배열 A와 B로 나눈 후 문제를 풉니다.

1. A의 부분수열을 찾고 목표하는 값 S에 도달하는지 확인합니다.
2. B의 부분수열을 찾고, 목표하는 값 S에 도달하는지 확인하면서, S-(A의 부분집합)에 도달하는지 확인합니다.
3. 부분수열을 찾는 방법은 재귀를 통해 찾습니다.

---

😎문제 풀이 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
  .map((v) => v.split(" ").map(Number));
const [N, S] = input[0];
const half = Math.floor(N / 2);
const left_arr = input[1].slice(0, half);
const right_arr = input[1].slice(half);

let answer = 0;
const left_map = {};
leftCircle(0, 0);
function leftCircle(sum, index) {
  if (index === half) return;
  const cur = left_arr[index];
  leftCircle(sum + cur, index + 1);
  leftCircle(sum, index + 1);
  if (left_map[sum + cur]) left_map[sum + cur]++;
  else left_map[sum + cur] = 1;
  if(S === sum+cur) answer++
}

rightCircle(0,0)
function rightCircle(sum, index) {
  if (index === N - half) return;
  const cur = right_arr[index];
  rightCircle(sum + cur, index + 1);
  rightCircle(sum, index + 1);
  if(left_map[S-sum-cur]) answer += left_map[S-sum-cur] 
  if(sum+cur === S) answer++
}

console.log(answer)