Baekjoon 3372번 보드 점프

문제

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

걸린 시간

-

풀이

TypeScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map((s: string) => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const n: number = parseInt(input());

const board: Array<Array<number>> = Array.from(Array(n), () => Array(n));

for(let i = 0; i < n; i++){
  const tmp: number[] = input().split(' ').map(Number);
  for(let j = 0; j < n; j++){
    board[i][j] = tmp[j];
  }
}

const dp: Array<Array<BigInt>> = Array.from(Array(n), () => Array(n).fill(-1n));

const solve: Function = (y: number, x: number): BigInt => {
  // 기저 사례
  if(y === n-1 && x === n-1) return 1n;
  if(!board[y][x]) return 0n;
  // 메모이제이션
  if(dp[y][x] !== -1n) return dp[y][x];
  // 재귀 호출
  let ret: BigInt = 0n;
  const move = board[y][x];
  if(x+move < n) ret += solve(y, x+move);
  if(y+move < n) ret += solve(y+move, x);
  return dp[y][x] = ret;
}

console.log(solve(0, 0).toString());

dp 에 큰 수 계산이 필요한 문제.

javascript 로 메모이제이션만 적용한 후 제출해보니 StackSizeExceeded 런타임 에러가 발생했다. 보드의 숫자가 0 일 때의 처리를 해주지 않아서 무한히 재귀호출 되었기 때문이었다.

• 처음엔 javascript 엔진의 재귀 깊이 제한 때문이라고 생각했지만 최대 N 값이 100 이기 때문에 재귀 호출 횟수는 2N 을 넘을 수가 없었다.
• 이상한 게 c++ 에서는 예외처리 없이도 3번 정도 재귀 호출되고 더 이상 반복되지 않는다.

큰 수 계산은 Big Integer 하면 생각나는 언어가 python 이었기 때문에 일단은 푼 뒤 나중에 찾아보니 es2020 부터는 BigInt 가 내장 객체로 지원된다고 javascript 로 다시 풀었다.