[백준] 14225번 부분수열의 합 - JavaScript(NodeJS)

문제

14225번: 부분수열의 합

 

풀이

1182번 문제 풀이 <- 다음의 문제와 거의 같은 유형이다.

 

다만 이 문제에서는, 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구한다.

 

풀이 방법

1182번 문제와 동일하게, 모든 부분수열의 합을 구한다.

 

수열 S의 크기 N이 1<=N<=20이고, S를 이루는 수는 자연수이며 10만보다 작으므로,
가장 작은 자연수를 구하기 위해 200만 크기의 배열을 선언하고 모든 원소를 0으로 초기화한다.

 

부분수열의 합을 구할 때 마다, 합에 해당하는 배열의 인덱스에 1을 넣어준다.

 

부분수열의 합을 모두 구했다면,
배열의 인덱스=1부터 순차적으로 조회하면서
인덱스에 들어있는 원소가 0이라면 바로 조회를 끝내고 출력해준다.

 

코드

const sol = (input) => {
  const N = +input[0];
  const S = input[1].split(" ").map(Number);
  const MAX_SUM = 2000001; // 10만 * 20 => 부분수열 합의 최대가 200만을 넘을 수 없다.
  const sumArr = new Array(MAX_SUM).fill(0);
  const pick = [];

  function dfs(L) {
    if (L === N) {
      const sum = pick.reduce((sum, val) => sum + val, 0);
      sumArr[sum] = 1;
      return;
    }
    pick.push(S[L]);
    dfs(L + 1);
    pick.pop();
    dfs(L + 1);
  }
  dfs(0);

  for (let i = 1; i < MAX_SUM; i++) if (!sumArr[i]) return i;
};


// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });