[백준_1890] 점프 python

생각보다 까다로웠다,

처음에 bfs로 풀려 했으나, 시간초과에 걸리고 말았기 때문이다.

# n 입력
n = int(input())

# grid 입력
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

# dp 설계
dp = [
    [0] * n
    for _ in range(n)
]

# dp 초기설정
dp[0][0] = 1

# dp 채워넣기
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 + grid[i][j] < n:
            # 이전까지 경로 수를 더해 줌
            dp[i][j + grid[i][j]] += dp[i][j]

        # 아래쪽으로 이동 가능한 경우
        if i + grid[i][j] < n:
            # 이전까지 경로 수를 더해 줌
            dp[i + grid[i][j]][j] += dp[i][j]