[백준] - 1890 점프 (node.js)

문제링크

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const n = Number(input[0]);
let l1 = [];
for (let i = 1; i <= n; i++) {
  l1.push(input[i].split(" ").map(Number));
}

let dp = Array.from({ length: n }, () => Array(n).fill(0n));
dp[0][0] = 1n;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    let k = l1[i][j];
    if (k === 0) continue;
    if (i + k < n) {
      dp[i + k][j] += dp[i][j];
    }
    if (j + k < n) {
      dp[i][j + k] += dp[i][j];
    }
  }
}

console.log(dp[n - 1][n - 1].toString());

풀이

dp로 풀었다. 모든 칸에 1이 적혀있을 경우 경우의 수가 JS의 Number보다 커져서 BigInt를 써야했다. ⭐⭐

처음엔 BFS로 풀어야하나 했는데 DP로 풀어야했다. 아래 메모 기억하기!

DP vs BFS ⭐⭐

경로 개수 ➡️ DP 누적
최단 거리/최소 단계 ➡️ BFS