[Python] 1520번 내리막 길

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

---

 

24/11/13

 

 

무난한 DP이다. 처음에는 바텀업으로 생각했으나, 잘 생각나지 않아서 탑다운으로 짰다.

---

 

문제 접근 방식:

 

 

DP식을 다음과 같이 정의하자.

 

DP[i][j] = $(i, j)$번째 칸에 왔을 때 항상 내리막 길로만 오는 경우의 수.

 

우리의 목적은 $DP[N-1][M-1]$의 값을 구하는 것이다.

 

또한, $DP[0][0] = 1$임을 알고 있다.

 

내리막 길로 간다는 것은 현재 칸보다 이전의 칸에 쓰여있는 숫자가 더 크다는 뜻이다.

 

따라서, 기본적으로 현재 칸을 둘러싸고 있는 4개의 주변 칸, 즉, 이전의 칸에 쓰여있는 숫자가 더 크다면, 그 칸을 통해 현재 칸으로 올 수 있다.

 

따라서, 4개의 주변 칸에 대해서 DP값을 찾아주고, 그 값을 전부 더한 값이 DP[i][j]의 값이 된다.

 

이를 토대로 탑다운 DP를 돌리면 되고, 파이썬의 경우 재귀 깊이의 제한이 있으니 이에 유의하여 재귀깊이를 설정해주면 될 것이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1520번 내리막 길
# DP
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500_000)

N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(N)]
DP = [[-1 for _ in range(M)] for _ in range(N)]
dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
DP[0][0] = 1
def dfs(i, j):
    K = 0
    if DP[i][j] != -1:
        return DP[i][j]
    for k in range(4):
        ni, nj = i+dr[k], j+dc[k]
        if 0 <= ni < N and 0 <= nj < M and G[i][j] < G[ni][nj]:
            if DP[ni][nj] == -1:
                dfs(ni, nj)
            K += DP[ni][nj]
    DP[i][j] = K
    return DP[i][j]
dfs(N-1, M-1)
print(DP[N-1][M-1])