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

안녕하세요 :)

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

문제 제대로 안읽어서 초반에 해맸네요 .. 조심하자...
경로길이가 아니라 최단 경로 "개수" 입니다.

풀이

고등학교때 풀던 장애물있는 최단거리개수 구하기 문제 기억하시나요.
이건 이렇게 풀면됩니다! 그래서 첫시작 (1, 1) 좌표에는 1로 시작합니다.
위 그림을 예시로 들자면 A점이 (1, 1) 이고 B가 우리가 구하고 싶은 (n, m) 이 되겠네요.
DP를 이용해서 구해줍니다.

def solution(m, n, puddles):
    d = [[0] * (m+1) for _ in range(n+1)]
    
    for puddle in puddles:
        a, b = puddle
        d[b][a] = -1
        
    d[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 d[i][j] != -1:
                d[i][j] = (d[i][j-1] + d[i-1][j]) % 1000000007
            else:
                d[i][j] = 0
    # print(d)    
    return d[n][m]