Programmers / 3단계 / 등굣길 / python / 동적계획법(Dynamic Programming)

 

https://school.programmers.co.kr/learn/courses/30/lessons/42898

 

 

모범 답안

def solution(m, n, puddles):
    puddles = [[q,p] for [p,q] in puddles]
    dp = [[0] * (m+1) for _ 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 [i, j] in puddles:
                dp[i][j] = 0
            else:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
    return dp[n][m]

웅덩이의 위치 puddles의 좌표가 반대로 되어있기 때문에 이를 주의하여 좌표를 반대로 적어주어야 한다.

dp를 초기화하고, 시작 위치인 dp[1][1]은 1로 설정한다. 

dp 테이블의 칸들을 순서대로 탐색한다.  현재 칸이 웅덩이일 경우 0으로 변환하고, 아닐 경우 왼쪽 칸과 위쪽 칸의 합을 1000000007로 나눈 값으로 변환한다.

 

 

참조

https://dev-note-97.tistory.com/141