[프로그래머스][동적계획법] 등굣길

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

코딩테스트 연습 - 등굣길

문재해결 방법

• dp[0][0] = 1로 둔다
• 한 지점에서 위쪽과 왼쪽의 dp값을 더한다.
• set을 이용해서 웅덩이는 무시한다.
• 문제에서 1,000,000,007 로 나눠주라는거 주의하자

 

 

def solution(m, n, puddles):
    answer = 0
    dp = [[0 for _ in range(m)] for _ in range(n)]
    dp[0][0] = 1
    isPuddle = set()
    for x, y in puddles:
        isPuddle.add((y-1,x-1))
    for y in range(n):
        for x in range(m):
            if (y,x) in isPuddle:
                continue
            if x - 1 >= 0:
                dp[y][x] = dp[y][x] + dp[y][x-1]
            if y - 1 >= 0:
                dp[y][x] = dp[y][x] + dp[y-1][x]

    answer = dp[n-1][m-1] % 1000000007
    return answer