점프

문제

언어

  • JavaScript

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기
  4. dp[n - 1][n - 1] 값 출력

문제 풀이 step 1

  • N x N 크기의 게임판에 수가 적혀져 있습니다. 이 게임판에서 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프해야 합니다.
  • 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미하며, 반드시 오른쪽이나 아래쪽으로만 이동해야 합니다.
  • 0 이 적힌 칸은 더 이상 이동이 불가능합니다. 무조건 현재 칸에 적혀있는 수만큼만 이동할 수 있습니다.
  • 그리고 한 번 점프 할 때, 방향 전환은 불가능합니다.
  • 위의 규칙을 지키며 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 이동할 수 있는 경로의 개수를 구하는 문제입니다.

문제 풀이 setp 2

  • dp[k][k] = [k, k] 칸에 도달할 수 있는 경로의 개수
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 점화식은 dp[k][k] = (위에서 내려오는 경우의 수) + (왼쪽에서 오른쪽으로 오는 경우의 수) 입니다.
    • 위에서 내려오는 경우의 수는
      • dp[k - 1][k], dp[k - 2][k], dp[k - 3][k], …, dp[0][k] 중에서 조건을 만족하는 경우만 더하면 됩니다.
      • 예를 들어, dp[k - 1][k] 의 board[k - 1][k] 가 1 이라면, dp[k][k] += dp[k - 1][k] 입니다.
      • 예를 들어, dp[k - 2][k] 의 board[k - 2][k] 가 2 라면, dp[k][k] += dp[k - 2][k] 입니다.
      • 예를 들어, dp[k - 3][k] 의 board[k - 3][k] 가 3 이 아닌 다른 값이라면, 이 경우는 더할 수 없습니다.
      • 즉, 현재 칸으로부터 떨어져 있는 칸의 개수가 칸에 적혀있다면, 경로의 수를 추가합니다.
      • 반면, 칸으로부터 떨어져 있는 칸의 개수와 다른 값이 칸에 적혀있다면 경로의 수를 추가할 수 없습니다.
    • 왼쪽에서 오른쪽으로 오는 경우의 수도 동일한 방식으로 구하면 됩니다.
  • dp 배열은 모두 0 으로 초기화 합니다. (BigInt 형은 0n 으로 초기화)
  • base 는 dp[0][0] 으로 값은 1 입니다. (BigInt 형은 1n 으로 초기화)
    • 가장 왼쪽, 가장 위쪽 칸에서 시작하기 때문입니다.
  • 우선, 점화식과 base 값을 이용해서 dp 배열을 다 채웁니다.
  • 그리고 가장 오른쪽, 가장 아래 칸에 도달할 수 있는 경로의 수 즉, dp[n - 1][n - 1] 을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.
  • 그리고 수의 범위가 크기 때문에 BigInt 형으로 계산해야 풀 수 있습니다.

소스 코드

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

const solution = (input) => {
	const n = Number(input[0]);
	const board = input.slice(1).map((v) => v.split(" ").map(Number));
	const dp = Array.from({length: n}, () => Array(n).fill(0n));

	// base
	dp[0][0] = 1n;

	// bottom-up
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			// 위에서 내려오는 경로의 수 계산
			for (let k = i - 1; k >= 0; k--) {
				if (board[k][j] === i - k) dp[i][j] += dp[k][j];
			}

			// 왼쪽에서 오른쪽으로 오는 경로의 수 계산
			for (let k = j - 1; k >= 0; k--) {
				if (board[i][k] === j - k) dp[i][j] += dp[i][k];
			}
		}
	}

	// BigInt 형이므로 String 으로 변환 후 출력
	return String(dp[n - 1][n - 1]);
};

console.log(solution(input));