[백준] 5557 1학년 - javascript

📌 문제

https://www.acmicpc.net/problem/5557

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let N = Number(input[0]);
const numbers = input[1].split(" ").map(Number);

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];
    }
  }
}
console.log(dp[N - 2][numbers[N - 1]].toString());

✔ 알고리즘 : 2차원 DP

✔ dp[i][j] : i번째 인덱스까지 사용하여 j를 만드는 경우의 수

✔ N번째 경우의 수는
1)N-1번째에 구한 경우의 수에서 다음 숫자를 더했을 때 20보다 작거나 같고

2)N-1번째에 구한 경우의 수에서 다음 숫자를 뺏을 때 0보다 크거나 같을 때

N-1번째의 경우의 수를 더해주면 N번째의 경우의 수가 나온다

❗ 등식의 개수는 2^63-1 이하이므로 기본 Number 자료형의 범위를 벗어나므로 BigInt 자료형을 사용해야함

✔ 난이도 : 백준 기준 골드5