프로그래머스 등굣길

https://programmers.co.kr/learn/courses/30/lessons/42898

dp문제를 처음 풀때는 어떻게 이걸 동적계획법으로 생각하고 풀 생각을 했을까? 라는 의문이 제일 먼저 들었다. 근데 dp문제를 계속해서 풀고 조금 적응이되니 dp로 풀어야겠다는 느낌이 강하게 들었다.

x,y지점에 대해서 최단거리가 아닌 최단거리의 개수를 구해야 한다.
x,y지점에서의 최단거리는 (x-1,y) 지점과 (x,y+1) 지점의 최단거리 개수의 합이다.
웅덩이 인곳만 제외하고 위의 로직을 구현해주면 된다.

def solution(m, n, puddles):
    answer = 0
    dp = [[0]*(m+1) for i in range(n+1)]
    dp[1][1] = 1
    for pud in puddles:
        dp[pud[1]][pud[0]] = -1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if dp[i][j] == -1:
                continue
            if dp[i-1][j] != -1:
                dp[i][j] += dp[i-1][j]
            if dp[i][j-1] != -1:
                dp[i][j] += dp[i][j-1]
    print(dp)
    return dp[n][m]%1000000007