[백준/Node.js] 1학년 #5557

짧은 썰

처음에 백트래킹으로 하다가 문제 조건을 보니 절대 불가능했다.
보다보니 떠올린 방법은 backtracking의 빠져나가는 조건을 더 좋게하거나 dp를 사용할 수 있는 방법을 생각해봤다. 하지만 어떻게 풀이를 작성해야 할지 아이디어가 생각나지 않았다. 결국 다른 사람의 풀이를 참고했다.
그런데 로직을 동일하게 JS로 구현했는데도 실패가 떠서 굉장히 당황했다.
JS만 이런건지 너무나 궁금해 다른 JS로 제출한 사람의 풀이를 참고해보니 결과값의 자료형이 BigInt였다.
알고보니 문제의 조건은 2^63 - 1까지 였고, 알아본 자바스크립트 기본 Number 자료형의 최대 크기는 2^53 - 1였다.
몰랐던 Number형의 최대 크기를 알게 해준 문제였다.(킹치만 Python으로 풀었더라면 이런거 고려할 필요도 없는데..ㅠ)

아무튼 중요한건 dp 로직을 떠올리지 못했다는 것이고, 다음에 풀 때는 문제조건을 잘 파악하고, 제시한 조건이 좁은 경우 메모리를 사용해 연산속도를 올리는 dp 풀이를 떠올리도록 노력해보자(

코드

const fs = require('fs');

const solution = (N, numbers) => {
  const dp = Array.from({ length: N - 1 }, () => new Array(21).fill(BigInt(0)));

  dp[0][numbers[0]] += BigInt(1);
  for (let i = 1; i < N - 1; i++) {
    for (let j = 0; j <= 20; j++) {
      if (dp[i - 1][j]) {
        if (j + numbers[i] <= 20) dp[i][j + numbers[i]] += dp[i - 1][j];
        if (j - numbers[i] >= 0) dp[i][j - numbers[i]] += dp[i - 1][j];
      }
    }
  }

  return dp[N - 2][numbers[N - 1]].toString();
};

input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input[0]);
const numbers = input[1].split(' ').map(Number);

console.log(solution(N, numbers));