[백준][dp] 1890 점프 NodeJs 구현

     

목차

 

문제

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

 

 

코드 구현 방향

dp까지는 생각해야 한다. 아래 문제와 유사한 문제이다.

https://be-senior-developer.tistory.com/269

[백준][dp] 1937 욕심쟁이 판다 NodeJs 구현

 

 

 

 

구현 시 주의점

범위가 매우 크기 때문에 Nodejs 구현 시 BigInt를 써주어야 한다.

또한 하양식으로 풀면 재귀호출의 깊이로 인해 틀리게 된다.

 

 

 

하향식 코드(틀린 코드)

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let dx = [BigInt(0), BigInt(1)];
let dy = [BigInt(1), BigInt(0)];

let N = BigInt(input[0]);
let board = [];
let idx = 1;

while (idx < input.length) {
  let t = input[idx].trim().split(" ").map(BigInt);
  idx++;
  board.push(t);
}

let dp = Array.from({ length: Number(N) }, () =>
  Array(Number(N)).fill(BigInt(0))
);

function dfs(x, y) {
  if (x === N - BigInt(1) && y === N - BigInt(1)) {
    return BigInt(1);
  }
  if (dp[Number(y)][Number(x)] !== BigInt(0)) {
    return dp[Number(y)][Number(x)];
  }

  let sz = board[Number(y)][Number(x)];
  for (let i = 0; i < 2; i++) {
    let nx = x + dx[i] * sz;
    let ny = y + dy[i] * sz;
    if (nx < BigInt(0) || nx >= N || ny < BigInt(0) || ny >= N) continue;
    dp[Number(y)][Number(x)] += dfs(nx, ny);
  }
  return dp[Number(y)][Number(x)];
}

dfs(BigInt(0), BigInt(0));
                                                                                                              
console.log(dp[0][0].toString());

 

 

상향식 코드

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let N = BigInt(input[0]);
let board = [];
for (let i = 1; i <= Number(N); i++) {
  board.push(input[i].trim().split(" ").map(BigInt));
}

// DP 배열 초기화
let dp = Array.from({ length: Number(N) }, () => Array(Number(N)).fill(BigInt(0)));
dp[0][0] = BigInt(1); // 시작점에서의 경로 수는 1

// 동적 프로그래밍 진행
for (let y = 0; y < Number(N); y++) {
  for (let x = 0; x < Number(N); x++) {
    if (dp[y][x] === BigInt(0) || (x === Number(N) - 1 && y === Number(N) - 1)) continue;
    let step = board[y][x];
    if (x + Number(step) < Number(N)) {
      dp[y][x + Number(step)] += dp[y][x];
    }
    if (y + Number(step) < Number(N)) {
      dp[y + Number(step)][x] += dp[y][x];
    }
  }
}

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