[BOJ/Python] 1520. 내리막 길

📌 문제

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

1520번: 내리막 길

 

📌 문제 접근 방법

1. 이것저것 내 생각으로 할 수 있는 모든 시도를 다 해본 것 같다!
   (그냥 dfs, 방문 체크 리스트를 아예 가지고 다니기 등등)
2. 결국 포기하고 구글링..! dp를 활용해야 하는 문제였다.
3. 출발점에서 시작해서 도착점까지 도달할 수 있다면, dp 리스트에 값을 + 해준다.
4. 이를 다 체크하면, (0, 0)에는 출발점에서 도착점까지 갈 수 있는 경우의 수가 남는다.

 

📌 코드

import sys
sys.setrecursionlimit(10000)

def dfs(x, y):
    if dp[x][y] == -1:
        dp[x][y] = 0

        for dx, dy in dxy:
            nx, ny = x+dx, y+dy

            if 0 <= nx < M and 0 <= ny < N and arr[nx][ny] < arr[x][y]:
                dp[x][y] += dfs(nx, ny)
    
    return dp[x][y]
    

M, N = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(M)]

dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

dp = [[-1 for _ in range(N)] for _ in range(M)]
dp[M-1][N-1] = 1

print(dfs(0, 0))