[파이썬🐍] 프로그래머스 : 등굣길

def solution(m, n, puddles):
    dp = [[0] * (m + 1) for i in range(n + 1)]  
    dp[1][1] = 1   #시작점
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if i == 1 and j == 1: continue 
            if [j,i] in puddles:   
                dp[i][j] = 0
            else:                   
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])
    return dp[n][m] % 1000000007

최단 거리이기 때문에 구하려는 좌표의 왼쪽과 위의 좌표만 가지고 더해주면 된다.

 

웅덩이는 0으로 넣어줘서 계산에 관여하지 않도록 한다.