파이썬)내리막길 -BOJ

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

1520번: 내리막 길

 

 

 

m, n = map(int, input().split())

arr = []
cnt = 0

for i in range(m):

    a = list(map(int, input().split()))

    arr.append(a)


dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

dp = [[-1] * n for _ in range(m)]


def dfs(sx, sy):
    if sx == m-1 and sy == n-1:
        return 1

    if dp[sx][sy] != -1:
        return dp[sx][sy]

    ways = 0
    for i in range(4):
        nx, ny = sx + dx[i], sy + dy[i]
        if 0 <= nx < m and 0 <= ny < n and arr[sx][sy] > arr[nx][ny]:
            ways += dfs(nx, ny)

    dp[sx][sy] = ways
    return dp[sx][sy]


print(dfs(0, 0))

이 문제는 dfs로만 풀다 결국 정답 참조한 뒤 dp를 더해 dfs + dp를 이용해 푼 문제이다.