[Programmers | Level 3] 등굣길 (Python)

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

코딩테스트 연습 - 등굣길

def solution(m, n, puddles):
    graph =[[0] * m for _ in range(n)]
    d = [[0] * m for _ in range(n)]
    
    for i in puddles:
        graph[i[1]-1][i[0]-1] = 1
        
    for i in range(1, m):
        if graph[0][i] == 1:
            break
        d[0][i] = 1
        
    for i in range(1, n):
        if graph[i][0] == 1:
            break
        d[i][0] = 1
    
    for i in range(1, n):
        for j in range(1, m):
            if graph[i][j] == 0:
                d[i][j] = (d[i-1][j] + d[i][j-1]) % 1000000007
                
    return d[n-1][m-1]

 

전형적인 DP 문제.

bottom-up 방식으로 점화식을 이용하여 해결하였다.

오른쪽과 아래로만 갈 수 있으므로,

오른쪽, 아래로 가면서 DP 테이블을 채운다.

위쪽과 왼쪽의 경우의 수를 합해주면 현재 칸의 경우의 수가 나온다.