1890 백준 파이썬

처음에 DFS로 시도했으나 시간초과에 부딪혔다.

import sys
input=sys.stdin.readline
n=int(input())
m=[]
for x in range(n):
    m.append(list(map(int,input().split())))
x=0
y=0
cnt=0
dp=[[0 for x in range(n)] for x in range(n)] 
dp[0][0]=1
def move(x,y,dp):
    if x==n-1 and y==n-1:
        return dp
    else:
        k=m[x][y]
        if x+k<n:
            dp[x+k][y]+=dp[x][y]
            move(x+k,y,dp)
        if y+k<n:
            dp[x][y+k]+=dp[x][y]
            move(x,y+k,dp)
move(0,0,dp)
print(dp[n-1][n-1])

입력받은 리스트의 값 + 현재위치가 n을 넘는지 확인한 뒤에 재귀함수로 직접 이동시켰다.

이러면 n이 1000이 넘어가기에 시간초과에 걸린다.

 

import sys
input=sys.stdin.readline
n=int(input())
m=[]
for x in range(n):
    m.append(list(map(int,input().split())))
x=0
y=0
cnt=0
dp=[[0 for x in range(n)] for x in range(n)] 
dp[0][0]=1
for x in range(n):
    for y in range(n):
        if (x==n-1 and y==n-1):
            print(dp[-1][-1])
        else:
            jump=m[x][y]
            if x+jump<n:
                dp[x+jump][y]+=dp[x][y]
            if y+jump<n:
                dp[x][y+jump]+=dp[x][y]

단순하게 반복문으로 dp를 진행시켜주면 된다.