[Python] 백준 1890 - 점프

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

1890번: 점프

 

처음에는 접근을 BFS와 DP를 섞어서 하면 될 것 같은데? 했지만 메모리초과가 나왔다.

BFS로 풀려고하면 생각보다 조건들이 까다로워져서 다른 방법을 생각해봤다.

 

그래서 생각해낸것이 이중 for문으로  전부 확인하면서 DP 돌리는거였다(진작에 이렇게 할걸..ㅋㅋㅋ)

DP에는 해당 위치로 올 수 있는 경로의 개수를 저장한다.

 

그리고 이중 for문을 돌릴 시 맨 마지막 (n-1, n-1) 번째는 continue로 패스해야한다.

jump값이 0이라서 출력할때 제자리 점프를 두 번 하고 값이 X4가 되어버리기 때문.

 

n=int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(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:
            continue
        jump = arr[i][j]
        if 0<=i+jump<n:
            dp[i+jump][j] += dp[i][j]
        if 0<=j+jump<n:
            dp[i][j+jump] += dp[i][j]

print(dp[n-1][n-1])