[Python] 프로그래머스 - 등굣길

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

코딩테스트 연습 - 등굣길

무난한 DP문제이다.

 

오른쪽과 아래로만 갈 수 있으므로 dp연산을 할 때 윗 좌표값, 왼쪽 좌표값만 고려해주면 된다.

def solution(m, n, puddles):
    dp = [[0] * m for _ in range(n)]
    dp[0][0] = 1
    # 물에 잠긴 곳은 -1 넣어줌
    if puddles:
        for i in puddles:
            dp[i[1] - 1][i[0] - 1] = -1
    # 1번째 행과 1번째 열은 따로 반복문을 돌려준다.
    for i in range(1, m):
        dp[0][i] = 0 if dp[0][i] == -1 else dp[0][i - 1]
    for i in range(1, n):
        dp[i][0] = 0 if dp[i][0] == -1 else dp[i - 1][0]
        
    for i in range(1, n):
        for j in range(1, m):
            # dp[i][j]가 물에 잠겼으면 다음 덧셈에 영향을 주지 않게 0으로 바꾼다.
            if dp[i][j] == -1:
                dp[i][j] = 0
            else:
                # dp[i][j] = 윗 좌표의 dp값 + 왼쪽 좌표의 dp값(오른쪽이나 아래로만 갈 수 있으므로)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] % 1000000007
                
    return dp[n - 1][m - 1]