이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 점화식을 구하기 위해 도식화 하였다.

board에 게임판을 입력하고 dp에 메모라이제이션을 진행하였다.

• dp[0][0]을 1로 갱신한다.
• dp[0][0]에서 갈 수 있는 칸에 해당하는 dp에 dp[0][0]을 더한다.
  -> dp[0][0]에서는 board[0][2], board[2][0]에 갈 수 있으므로 dp[0][2], dp[2][0]에 1을 더해준다.
• 이 과정을 dp[n-1][n-1]에 도달할 때까지 반복한다.

이 과정을 통하여 다음과 같은 점화식을 도출하였다.
dp[i+board[i][j][j]+=dp[i][j], dp[i][j+board[i][j]]+=dp[i][j]

• n을 입력받는다.
• 게임판을 입력받을 리스트 board를 선언한다.
• n번 반복하는 for문을 돌린다.
  -> board를 입력받는다.
• dp를 n*n의 크기에 0을 채워 선언한다.
• dp[0][0]을 1로 갱신한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> n번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 i가 n-1이고 j가 n-1일 경우 dp[i][j]를 출력하고 반복문을 탈출한다.
  --> 만약 j+board[i][j]가 n보다 작을 경우 dp[i]j+board[i][j]]에 dp[i][j]를 더해준다.
  --> 만약 i+board[i][j]가 n보다 작을 경우 dp[i+board[i][j]][j]에 dp[i][j]를 더해준다.

Code

n=int(input())
board=[]
for _ in range(n):
    board.append(list(map(int, input().split())))
dp=[[0]*n for _ in range(n)]
dp[0][0]=1
for i in range(n):
    for j in range(n):
        if i==n-1 and j==n-1:
            print(dp[i][j])
            break
        if j+board[i][j]<n:
            dp[i][j+board[i][j]]+=dp[i][j]
        if i+board[i][j]<n:
            dp[i+board[i][j]][j]+=dp[i][j]