[Python/파이썬] 백준 3372번 보드 점프

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

 

코드

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*n for _ in range(n)]
dp[0][0] = 1
for i in range(n):
    for j in range(n):
        if board[i][j] == 0:
            continue
        # 오른쪽
        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]
print(dp[n-1][n-1])

 

dp[i][j]는 (i, j)까지 갈 수 있는 경로의 수를 저장한다. 출발점인 (0, 0)의 dp값을 1로 놓고, N × N 게임 보드의 각 칸을 살펴보며 현재 칸(i, j)에서 오른쪽과 아래로 board[i][j]만큼 이동할 수 있다면 현재 칸 (i, j)까지 올 수 있는 경로의 수인 dp[i][j]를 이동한 칸의 dp 값에 더해주면 된다.