백준 / 1520 / 내리막 길 / 파이썬, python, pypy

1520번: 내리막 길

처음에 문제를 보자마자 dfs를 생각했고, 아무 생각없이 문제를 풀었더니 시간초과가 발생하였다.

 

문제를 다시보니 아래 또는 오른쪽으로만 이동 가능한게 아니라 돌아서 오는 경우를 생각해야했다.

 

dp를 사용해야한다 생각해서 dfs(x, y)는 x, y에서 출발하여 N-1, M-1까지 가는 경로의 수로 정의하고 dp 배열에 값을 저장하는 식으로 풀이하였다.

 

import sys
sys.setrecursionlimit(10**9)
 
direction = ((-1, 0), (1, 0), (0, -1), (0, 1))
 
# dfs(x, y) -> (x, y)에서 출발하여 (N-1, M-1)까지 가는 경우의 수
def dfs(x, y):
    if x == N-1 and y == M-1: return 1
    if dp[x][y] != -1: return dp[x][y]
 
    dp[x][y] = 0
    for dx, dy in direction:
        nx, ny = x + dx, y + dy
        if not (0 <= nx < N and 0 <= ny < M) or board[x][y] <= board[nx][ny]:
            continue
        dp[x][y] += dfs(nx, ny)
 
    return dp[x][y]
 
N, M = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [[-1]*M for _ in range(N)]
 
print(dfs(0, 0))