[프로그래머스/Python] 동적계획법(DP) - 등굣길

풀이

def solution(m, n, puddles):
    answer = 0
    DP = [[0]*(m+1) for i in range(n+1)]
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            if i==1 and j==1: #(1,1)은 1으로 초기화
                DP[1][1] = 1
            elif [j,i] not in puddles: # 물웅덩이가 아닌경우
                DP[i][j] = DP[i-1][j] + DP[i][j-1]      
    return DP[n][m] % 1000000007

# DP
[[0, 0, 0, 0, 0], 
[0, 1, 1, 1, 1], 
[0, 1, 0, 1, 2], 
[0, 1, 1, 2, 4]]

• DP를 사용하는 문제: 왼쪽 위 집에서부터 하나씩 모든 경우의 수를 계산하며 학교로
• 예시로 (2,3)으로 가는 방법은 왼쪽에서 오는 방법과 위에서 오는 방법이 있다. 왜냐하면 최단 경로로 가기 위해서는 (1,1)에서 오른쪽이나 아래로만 움직여야하기 때문이다. 따라서 (2,3)으로 오는 방법은 (1,3) 또는 (2,2)에서 출발해야하는 것
• 물웅덩이에서는 아예 이동을 할 수 없으므로 항상 0의 값을 갖게 한다.
• 점화식 DP[i][j] = DP[i-1][j] + DP[i][j-1]