(Python/LV3) 등굣길

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

풀이:

def solution(m, n, puddles):
    dp = [[0]*(m+1) for _ in range(n+1)]
    dp[1][1] = 1
    for i, j in puddles: # 웅덩이가 있는 곳은 -1로 표시
        dp[j][i] = -1
    for x in range(1,n+1):
        for y in range(1,m+1):
            if dp[x][y] == -1:
                dp[x][y] = 0
                
            else:dp[x][y] += (dp[x-1][y] + dp[x][y-1]) % 1000000007
    return dp[n][m]

 

dp = [[0]*(m+1) for _ in range(n+1)]
dp[1][1] = 1

# dp 판 만들어줌 맨윗줄 맨 왼쪽줄을 0 을 추가해줘야하기때문에 각 행열 +1 을 해준다

for i, j in puddles: # 웅덩이가 있는 곳은 -1로 표시
    dp[j][i] = -1
    
# 문제가 쓰레기다 행렬이 반대로 들어간다 질문하기 보고 앎

 

for x in range(1,n+1):
    for y in range(1,m+1):
        if dp[x][y] == -1:
            dp[x][y] = 0
        else:dp[x][y] += (dp[x-1][y] + dp[x][y-1]) % 1000000007
return dp[n][m]

# 행렬을 쭉 돌면서 웅덩이를 만나면 0 으로 바꿔준다. 나머지는 점화식에 따라푼다.
# 마지막 목적지 리턴

 

점화식은 해당지점까지 가는 최솟값을 하나하나 저장한다.

 

해당 위치에 왼쪽과 위에를 더한값이 최소값.