1890 점프

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

#dp

1890번: 점프

#1890 점프

import sys
input=sys.stdin.readline
#스탠다드 인풋

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

dp=[[0 for i in range(n)] for j in range(n)]
#dp 생성

dp[0][0]=1
#시작점 dp 는 1 (개수이므로 시작점으로 오는 경우의 개수 1)

for i in range(n):
    d=list(map(int,input().split()))
    for j in range(n):
        if dp[i][j]==0:
            continue
#만약 시작점을 거치지 않았다면 0

        if i+d[j]<n:
            dp[i+d[j]][j]+=dp[i][j]
        if j+d[j]<n:
            dp[i][j+d[j]]+=dp[i][j]

#x y값이 조건에 맞는지를 확인하여 out of range 를 걷어낸 후 경우의 수 입력

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

 

#마지막에 있는 것도 for문을 돌았을 것이기 때문에 (답+답)+(답+답) 을 거쳐서 dp[n-1][n-1]이 나왔을 것이다. 나누기 4 를 해준다.

 

#사소한 실수가 엄청난 시간을 잡아먹어버렸다. 마지막 수도 돈다는 것을 아는데는 케이스를 하나하나 뜯어보고 찾았다. 아직 많이 부족하다 열심히 하자..