❓ Problem

N × N 게임 보드에 양의 숫자들이 적혀있다. 목적은 왼쪽 위에서 오른쪽 아래까지 규칙에 맞게 점프를 해서 가는 것이다. 숫자들은 현재 점에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 갈 수 있으며 0은 더 이상의 진행을 막는 종착점이다. 다시 말해서 현재 점의 숫자만큼 오른쪽이나 아래쪽으로 가야한다는 의미이다.

🤔 How

• 각 칸을 기준으로 board[y][x] 값만큼 우측이나 아래로 이동할수있다.(보드 내에서)
• 종착지에 도착하는 방법의 가짓수를 알아내는게 목표이기에 각 경로마다 도착할수있는 방법의 가지수를 dp 테이블에 기록하는 형태로 만들어준다.
• c,java에서는 int값을 초과하는 단위가 있을수있어 bigInt에 대한 처리를 따로해주어야한다.

❗ Solve

# 보드점프
import sys
from collections import deque
input = sys.stdin.readline


def drawboard(n):  # board 그리기
    board = []
    for _ in range(n):
        board.append(list(map(int, input().split())))
    return board
    pass


def solution():
    n = int(input())
    board = drawboard(n)
    dp = [[0]*n for _ in range(n)]
    dp[0][0] = 1
    for y in range(n):
        for x in range(n):
            if v := board[y][x]:
                if y+v < n:
                    dp[y+v][x] += dp[y][x]
                if x+v < n:
                    dp[y][x+v] += dp[y][x]
    return dp[-1][-1]


if __name__ == "__main__":
    print(solution())
    pass