반응형 동적프로그래밍 등굣길1 [파이썬🐍] 프로그래머스 : 등굣길 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으로 넣어줘서 계산에 관여하지 않도록 한다. 2021. 7. 18. 이전 1 다음 반응형