[백준 1520번] 내리막길 - python

문제 링크

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

1520번: 내리막 길

 

풀이 

- 처음엔 재귀를 사용해서 풀었는데 시간 초과가 발생하였다. 

# 시간 초과 발생 
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def sol(x, y):
    global cnt 
    if x == m-1 and y == n-1:
        cnt += 1 
        return 
    
    if x != m-1 :
        if graph[x][y] > graph[x+1][y]:
            sol(x+1,y)
            
    if y != n-1 :
        if graph[x][y] > graph[x][y+1]:
            sol(x,y+1)
   
    if x != 0:
        if graph[x][y] > graph[x-1][y]:
            sol(x-1, y)
         
    if y != 0 :
        if graph[x][y] > graph[x][y-1]:
            sol(x,y-1)
        
        
m, n = map(int,input().split())

graph = []

for _ in range(m):
    graph.append(list(map(int,input().split())))
    
cnt = 0 
sol(0,0)
print(cnt)

- dp의 메모제이션을 사용해서 이미 경로의 수를 구한 위치에서는 다시 구하지 않고, dp에 저장된 값만 불러오도록 수정해주었다. 

import sys 
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

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

def sol(x, y):
	# 오른쪽 맨 끝 도착했으면 1 리턴 
    if x == m-1 and y == n-1:
        return 1 
    
    # 이미 방문했던 곳이면 저장된 경로의 수 바로 리턴 
    if dp[x][y] != -1:
        return dp[x][y]
        
    cnt = 0 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < m and 0 <= ny < n  and graph[x][y] > graph[nx][ny]:
            cnt += sol(nx,ny)
    
    # 경로 수 갱신     
    dp[x][y] = cnt 
    
    return dp[x][y]   
        
m, n = map(int,input().split())

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