[백준] 1890 점프 - javascript

📌 문제

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

📌 풀이

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]);
let arr = new Array(n).fill(new Array(n));
for (let i = 0; i < arr.length; i++) {
  arr[i] = input[i + 1].split(" ").map(Number);
}
let dp = new Array(n);
for (let i = 0; i < dp.length; i++) {
  dp[i] = new Array(n).fill(BigInt(0));
}
dp[0][0] = BigInt(1);
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    let num = arr[i][j];
    if (num === 0) continue;
    if (i + arr[i][j] < n) {
      dp[i + arr[i][j]][j] += dp[i][j];
    }
    if (j + arr[i][j] < n) {
      dp[i][j + arr[i][j]] += dp[i][j];
    }
  }
}
console.log(dp[n - 1][n - 1].toString());

✔ 알고리즘 : DP

✔ DP[i][j] = (i,j) 좌표 까지 갈 수 있는 경로의 경우의 수

✔ arr[i][j]가 0이면 진행을 막는 종착점이므로 continue

✔ i(행이동,아래로 점프)를 이동했을때 범위를 벗어나지 않는 경우 이동했을때의 좌표의 DP값에 현재 좌표의 DP값을 더해준다

✔ j(열이동,오른쪽으로 점프)를 이동했을때 범위를 벗어나지 않는 경우 이동했을때의 좌표의 DP값에 현재 좌표의 DP값을 더해준다

✔ 점화식

if (i + arr[i][j] < n) {
  dp[i + arr[i][j]][j] += dp[i][j];
}
if (j + arr[i][j] < n) {
  dp[i][j + arr[i][j]] += dp[i][j];
}

❗ 경로의 개수는 263-1보다 작거나 같다 라는 조건이 있기 때문에 Number형 변수를 쓰면 안되므로 BigInt자료형을 사용해야 한다

✔ 난이도 : 백준 기준 실버 2