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

https://programmers.co.kr/learn/courses/30/lessons/42898?language=python3

풀이방법

규칙을 찾아보자. 아래 혹은 오른쪽으로만 갈 수 있으므로,
dp[i][j] 는 위쪽(dp[i-1][j])과 왼쪽(dp[i][j-1])에서 들어오는 경우를 합산한 결과이다. 즉

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

라는 규칙을 확인할 수 있다.

폭우로 잠겨있는 배열은 0 값을 넣어주면 된다.

코드

def solution(m, n, puddles):
    answer = 0
    dp = [[0 for i in range(m)] for j in range(n)] # n:행, m:열
    dp[0][0] = 1 # 시작점 선언
    
    for i in range(n):
        for j in range(m):
            if [j+1,i+1] in puddles:
                dp[i][j] = 0
            else:
                if i == 0 and j == 0:
                    continue
                elif i == 0:
                    dp[i][j] = dp[i][j-1]
                elif j == 0:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
    
    return dp[-1][-1]