# BOJ - 1520 - 내리막 길

Updated:

``````
import sys

def solve(row, column, dp, data, R, C):

if dp[row][column] == -1:
dp[row][column] = 0
else:
return

if row - 1 >= 0 and data[row - 1][column] > data[row][column]:
if dp[row - 1][column] < 0:
solve(row - 1, column, dp, data, R, C)
dp[row][column] += dp[row - 1][column]

if row + 1 < R and data[row + 1][column] > data[row][column]:
if dp[row + 1][column] < 0:
solve(row + 1, column, dp, data, R, C)
dp[row][column] += dp[row + 1][column]

if column - 1 >= 0 and data[row][column - 1] > data[row][column]:
if dp[row][column - 1] < 0:
solve(row, column - 1, dp, data, R, C)
dp[row][column] += dp[row][column - 1]

if column + 1 < C and data[row][column + 1] > data[row][column]:
if dp[row][column + 1] < 0:
solve(row, column + 1, dp, data, R, C)
dp[row][column] += dp[row][column + 1]

def solution():
data = []
dp = [[-1 for _ in range(M)] for _ in range(N)]

dp[0][0] = 1
for i in range(N):

for i in range(N):
for j in range(M):
solve(i, j, dp, data, N, M)

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

``````

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

Categories:

Updated: