백준 1890 < 점프 > JavaScript

📍문제 링크

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

1890번: 점프

 

📍알고리즘 분류

- 다이나믹 프로그래밍

 

📍문제 풀이

N * N (4 <= N <= 100) 의 2차원 배열에 0~9 사이의 수가 배치되어 있다

 

좌표에서 오른쪽, 아래쪽으로만 이동 가능하며, 좌표의 숫자만큼 칸을 이동한다고 할 때,

좌상단에서 우하단으로 이동하는 가능한 방법의 수를 구하라

 

고등학교 시절 비슷한 문제를 풀었던것 같다

예를 들면, 1칸씩 오른쪽, 아래쪽으로 이동 가능하다고 할 때 각 칸으로 갈 수 있는 경로의 수는 아래와 같다

 

즉 위, 왼쪽에서 올 수 있는 경로의 수를 더하면 된다

 

이처럼 최종 지점까지 도달하는 방법의 수는, 이전의 각 마일스톤까지의 방법의 수의 영향을 받게 된다

- 이렇게 메모이제이션이 가능하다는 점에서 다이나믹 프로그래밍을 적용할 수 있다

 

2차원 메모이제이션 배열을 만들고, 각 좌표에는 도달할 수 있는 가능한 방법의 가짓수를 기록해나가면 된다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const N = +input.shift();
  const board = input.map((row) => row.split(" ").map(Number));
  // 아예 memo를 여유있게 넉넉하게 만들기
  const memo = Array.from({ length: N + 10 }, (_) =>
    Array.from({ length: N + 10 }, (_) => 0n),
  );
  // 최초의 방법의 수를 1로 초기화
  memo[1][1] = 1n;
  // memo 업데이트
  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= N; j++) {
      const val = board[i - 1][j - 1];
      if (val) {
        memo[i][j + val] += BigInt(memo[i][j]);
        memo[i + val][j] += BigInt(memo[i][j]);
      }
    }
  }
  console.log(memo[N][N].toString());
});