Written by 최태열
on 

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

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

코드

def solution(m, n, puddles):
    board=[[0]*(n+1) for _ in range(m+1)]
    
    board[0][1]=1
    for x in range(1,len(board)):
        for y in range(1,len(board[x])):
            if [x,y] in puddles:
                continue
            board[x][y]=board[x-1][y]+board[x][y-1]
    
    return board[-1][-1]%1000000007

dp로 풀었다.

결국 한 지점에 도달할 수 있는 경우의 수는

자기보다 한칸 전의 수를 더한 값이다.

따라서 저렇게 그냥 board[x][y]=board[x-1][y]+board[x][y-1] 만으로도 풀 수 있다.

다만, 0으로 초기화했기 때문에 board[1][1]이 1이 될 수 있도록 board[0][1]을 1로 만들어줬다.

그리고 puddle인 곳도 건너뛰게 했다.

Discussion and feedback