1520번 내리막길(dps+dp)

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

1520번: 내리막 길

문제정의

입출력

간단한 생각 정리

예전에 확률과 통계에서 점 by 점으로 이동하며 어떤 점에서 도착하는 경우의 수는 주변 점들에서의 경우의 수의 합과 같다는 논리를 사용하고 싶었다.

처음에는 dfs로 접근했는데 당연히 시간초과가 났고(예상했고)

두번째는 dp로 접근했는데 이동하는 경로가 단순하지가 않아서 실패(예상 못함)

그런데 문제 질문에 dfs+dp로 풀라고 해서 고민을 좀 해봤다.

나는 재귀함수의 가장 중요한 방법은 재귀가 알아서 해줄거야~ 라는 생각을 갖는 것이라고 생각한다

'어떤 점에서의 도착까지 경우의 수는 재귀함수로 처리한다.'는 게 main idea
코드에서는 이런식으로 구현했다.

dfs(x_2,y_2)
check[x][y]+=check[x_2][y_2]

x,y로부터 상하좌우 이동 좌표인 x_2,y_2들에 대해
x_2,y_2 부터 도착지점까지의 경우를 구하고 싹 다 더해준다. 그러면 끝!

그러면 dfs에서 시간초과가 난 이유인 같은 지점을 계속 반복한다는 문제가 해결된다.

아래는 python code

import sys

sys.setrecursionlimit(100000)

move =[(1,0),(-1,0),(0,-1),(0,1)] #하상좌우
#dfs를 재귀로 짜서 방문하지 않은 지점에서 최단거리를 구하고 방문한 지점은 그 값을 그냥 쓰자.
#dfs + dp
def dfs(x,y):
    global M
    global N
    global check
    global mapping


    if(check[x][y] == -1):
        check[x][y] = 0
        for i in range(0,4):
            x_2 = x + move[i][0]
            y_2 = y + move[i][1]

            if M>x_2>=0 and N>y_2>=0 and mapping[x][y]>mapping[x_2][y_2]:
                dfs(x_2,y_2)
                check[x][y]+=check[x_2][y_2]
    else:
        return


M,N = map(int,input().split())
check = [[-1 for i in range(N)] for j in range(M)]
mapping = [0 for i in range(M)]
for i in range(M):
    mapping[i] = list(map(int,sys.stdin.readline().split()))
check[M-1][N-1] = 1
dfs(0,0)

print(check[0][0])