알고리즘
파이썬)내리막길 -BOJ
1일1공부실천하자
2023. 8. 6. 01:18
https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
m, n = map(int, input().split())
arr = []
cnt = 0
for i in range(m):
a = list(map(int, input().split()))
arr.append(a)
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
dp = [[-1] * n for _ in range(m)]
def dfs(sx, sy):
if sx == m-1 and sy == n-1:
return 1
if dp[sx][sy] != -1:
return dp[sx][sy]
ways = 0
for i in range(4):
nx, ny = sx + dx[i], sy + dy[i]
if 0 <= nx < m and 0 <= ny < n and arr[sx][sy] > arr[nx][ny]:
ways += dfs(nx, ny)
dp[sx][sy] = ways
return dp[sx][sy]
print(dfs(0, 0))이 문제는 dfs로만 풀다 결국 정답 참조한 뒤 dp를 더해 dfs + dp를 이용해 푼 문제이다.