[JS/알고리즘] 백준 1890번 : DP

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 2^63-1보다 작거나 같다.

 

 

풀이

최초에 Stack을 사용해서 구현 문제로 접근했었다. DP로 접근할 경우 모든 배열을 순차적으로 탐색해야하지만, Stack을 사용하면 이동 가능한 배열만 계산 할 수 있을 것 같았다. 결국 예외처리에서 애를 먹어 DP로 재 접근하였다.

간단하게 모든 배열을 순차 탐색하면서 점프 가능한 위치에 이전 횟수를 더해주면 되는 간단한 로직이다.

 

이 문제의 키 포인트는 알고리즘이 아니라 결과 값이 2^63-1까지도 나올 수 있다는 것이다.

Javascript를 사용하기 때문에 반드시 이런 경우 BigInt 타입을 사용해야하며, 출력시에도 toString()을 사용해야 정답으로 인식된다.

 

 

해결 코드

function solve(n, table, dp) {
  for (let y = 0; y < n; y++) {
    for (let x = 0; x < n; x++) {
      let value = table[y][x];
      if (value === 0) continue;
      if (y + value < n) {
        dp[y + value][x] += BigInt(dp[y][x]);
      }
      if (x + value < n) {
        dp[y][x + value] += BigInt(dp[y][x]);
      }
    }
  }
}

function input() {

   const input = require("fs")
     .readFileSync("/dev/stdin")
     .toString()
     .trim()
     .split("\n");

  const n = +input.shift();
  const table = input.map((e) => e.split(" ").map((e) => +e));

  let dp = new Array(n).fill([]).map((x) => new Array(n).fill(BigInt(0)));

  dp[0][0] = 1;

  solve(n, table, dp);
  console.log(dp[n - 1][n - 1].toString());
}

input();

간단한 배열 초기화를 위해 Array(n).fill()을 기억하자.