[JS][백준]1890_점프

문제 번호

1890번: 점프

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 풀이

 DP[i][j]는 좌표 (i,j)에 도달 할 수 있는 경우의 수 이다.

움직일 수 있는 방향은 오른쪽과 아래 2곳 뿐이다. 

 

 2차원 배열 DP를 해당칸의 숫자만큼 오른쪽, 아래로 이동가능한지 확인하고 이동 가능하다면 jump 만큼 이동한 칸에 경우의 수를 증가시켜준다. 더해지는 칸 입장에서 보면 위, 왼쪽에서 오는 경우들이 더해지는 중이다.

 

근데 문제에서 '경로의 개수는 263-1보다 작거나 같다.' 라고 하였으므로 BigInt를 사용하여야 한다.

 

전체코드

function sol(N, game, DP) {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (DP[i][j] === 0 || ((i === N - 1) && (j === N - 1))) continue;
      else {
        let jump = game[i][j];
        let down = i + jump;
        let right = j + jump;

        if (down < N) DP[down][j] += BigInt(DP[i][j]);
        if (right < N) DP[i][right] += BigInt(DP[i][j]);
      }
    }
  }
}

function insert() {
  const fs = require('fs').readFileSync('점프/input.txt');
  let input = fs.toString().trim().split('\n');

  const N = Number(input.shift());
  input = input.map(x => x.split(' ').map(x => Number(x)));
  let DP = new Array(N).fill(null).map(x=>new Array(N).fill(BigInt(0)));
  DP[0][0] = 1; 

  sol(N, input, DP);
  console.log(DP[N - 1][N - 1].toString());
}

insert();

 

특이사항