백준 1890(점프) - Python(파이썬) - 다이나믹

1890번: 점프

처음 생각한 풀이는 다이나믹 프로그래밍이아니라 DFS를 생각해서 풀었다.

근데 시간제한에 걸리는걸로봐서 다이나믹 프로그래밍으로 다시 풀었다.

예제 설명

array 테이블

① dp 테이블로 모두 다 0을 만들기

첫번째 줄 ( i=0 ) 

② dp 테이블 가장 왼쪽 위 칸(dp[0][0]) =1 

③ array 테이블에서 array[0][0]의 값이 2이므로 

    오른쪽 +2 -> dp[0][0+2] = dp[0][0]+dp[0][2]

     아래쪽 +2 -> dp[0+2][0] = dp[0][0] +dp[2][0]

④ array 테이블에서 array[0][2]의 값이 3이므로

오른쪽 +3 -> n 넘어가기 때문에 X

왼쪽 +3 -> dp[0+3][2]=dp[0][2]+dp[3][2]

첫번째 줄 ( i=2 ) 

⑤ array 테이블에서 array[2][0]의 값이 1이므로 

    오른쪽 +1 -> dp[2][0+1] = dp[2][0]+dp[0][1]

     아래쪽 +1 -> dp[2+1][0] = dp[2][0] +dp[3][0]

⑥ array 테이블에서 array[2][1]의 값이 2이므로 

    오른쪽 +2 -> dp[2][1+2] = dp[2][1]+dp[2][3]

     아래쪽 +2 -> n 넘어가기 때문에 X

⑦ array 테이블에서 array[2][3]의 값이 1이므로

오른쪽 +1 -> n 넘어가기 때문에 X

왼쪽 +1 -> dp[2+1][3]=dp[2][3]+dp[3][3]

첫번째 줄 ( i=3 ) 

⑧ array 테이블에서 array[3][0]의 값이 3이므로 

    오른쪽 +3 -> dp[3][0+3] = dp[3][0]+dp[3][3]

     아래쪽 +3 -> n 넘어가기 때문에 X

⑨ array 테이블에서 array[3][2]의 값이 1이므로 

    오른쪽 +1 -> dp[3][2+1] = dp[3][2]+dp[3][3]

     아래쪽 +1 -> n 넘어가기 때문에 X

 

---

문제 풀이

① dp 테이블을 선언하고 왼쪽 맨위의 값을 1로 변경
②
i + array[ i ][ j ]값이 n을 넘지 않을 경우 -> dp[ i+array[i][j] ][ j ] += dp[ i ][ j ]
j + array[ i ][ j ]값이 n을 넘지 않을 경우 -> dp[ i ][ j+array[i][j] ] += dp[ i ][ j ]

import sys
n = int(sys.stdin.readline())
array = []
for i in range(n):
    array.append(list(map(int,sys.stdin.readline().split())))

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

dp[0][0]=1
for i in range(n):
    for j in range(n):
    	#n-1이고 n-1일 경우 그만두기
        if i==n-1 and j==n-1:
            break
        if i+array[i][j]<n:
            dp[i+array[i][j]][j]+=dp[i][j]
        if j+array[i][j]<n:
            dp[i][j+array[i][j]]+=dp[i][j]


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