[Python/파이썬] 프로그래머스 등굣길

프로그래머스

코드

def solution(m, n, puddles):
    dp = [[0 for _ in range(m+1)] for _ in range(n+1)]   
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1 and j == 1:
                dp[i][j] = 1
                continue
            if [j, i] not in puddles:  # 물에 잠긴 지역이 아니라면
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
            else:   # 물에 잠긴 지역이라면
                dp[i][j] = 0
    return dp[n][m]

맞게 한 거 같은데 자꾸 틀리길래 뭔가 하고 봤더니 문제에서 물이 잠긴 지역의 좌표를 줄 때 행, 열 순서가 아닌 열, 행 순서로 주고 있었다...문제를 잘 읽고 풀도록 하자...

 

오른쪽과 아래쪽으로만 움직일 수 있기 때문에 어떤 칸으로 최단거리로 갈 수 있는 방법은 그 칸의 위 칸까지 최단거리로 가는 방법과 왼쪽 칸까지 최단거리로 가는 방법의 합이다. 수식으로 알기 쉽게 나타내면 아래와 같다.

dp[i][j] = dp[i-1][j] + dp[i][j-1]