백준 1520. 내리막 길

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

1520번: 내리막 길

def dfs(i, j):
    if i == m - 1 and j == n - 1:  # 도착 지점에 도달
        return 1  # 경우의 수 1

    if dp[i][j] == -1:  # 탐색하지 않은 곳이면?
        dp[i][j] = 0  # 탐색

        for ti, tj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ni, nj = i + ti, j + tj
            if 0 <= ni < m and 0 <= nj < n and arr[i][j] > arr[ni][nj]:
                dp[i][j] += dfs(ni, nj)  # (i,j)부터 도착지점까지 갈 수 있는 경우의 수 업뎃

    # 탐색한 곳이라면? 그 위치에서 출발하는 경우의 수 리턴
    return dp[i][j]


m, n = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(m)]
dp = [[-1] * n for _ in range(m)]
print(dfs(0, 0))

dp를 더 공부해야 될 것 같다...ㅠㅠ 어렵다. 

+ 24.10.24

import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

def recur(y,x):

    if y == m-1 and x == n-1:
        return 1

    # 한번 계산된 값 재사용
    if dp[y][x] != -1:
        return dp[y][x]

    res = 0
    # 동서남북 탐색
    for dy, dx in [[1,0], [-1,0], [0,1], [0,-1]]:
        ny = y + dy
        nx = x + dx

        # 유효한 범위인지 확인
        if 0 <= ny < m and 0 <= nx < n:
            # 이동하려는 곳이 더 작은 경우
            if arr[y][x] > arr[ny][nx]:
                res += recur(ny,nx)

    dp[y][x] = res # 계산된 값을 DP 테이블에 저장 -> 추후 재사용
    return res

m, n = map(int, input().split())
arr = [list(map(int,input().split())) for _ in range(m)]
dp = [[-1]*n for _ in range(m)]

print(recur(0,0))