백준-1520-내리막 길

문제

내리막 길

풀이

문제조건 해석

내리막 길에서 이동 가능한 경로의 수 구하는 문제.

알고리즘

DP문제

• 재귀로 추상화하기 적합한 문제
• 재귀 이용할 때는 항상 recursionlimit 설정해주기

코드

from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(500*500)

m, n = [int(x) for x in input().rstrip().split()]
maps = []
for _ in range(m):
    maps.append([int(x) for x in input().rstrip().split()])


# DFS+DP로 풀어보자
def memo(func):
    cache = {}
    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrapper


@memo
def dfs(i, j):
    if (i, j) == (m-1, n-1):
        return 1
    cnt = 0
    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if not (0 <= i+di < m and 0 <= j+	dj < n):
            continue
        if maps[i+di][j+dj] < maps[i][j]:
            cnt += dfs(i+di, j+dj)
    return cnt


print(dfs(0, 0))

배운점

점화식을 세우는 것이 적합한 DP / 재귀가 적합한 DP 잘 구분해야겠다.