(파이썬) 등굣길 - 동적계획법

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

코딩테스트 연습 - 등굣길

def solution(m, n, puddles):
    arr = [[0 for _ in range(m)] for _ in range(n)]  # 경로를 담을 배열을 만듭니다. 
    arr[0][0] = 1  # 집의 위치에는 1이 들어가야 합니다. 
    for puddle in puddles:  # 웅덩이를 반영합니다.
        arr[puddle[1] - 1][puddle[0] - 1] = None
    for i in range(n):
        for j in range(m):
            if arr[i][j] is not None:  # 좌표 상 위의 경우의 수와 좌의 경우의 수의 합이 됩니다.
                arr[i][j] += 0 if arr[i - 1][j] is None else arr[i - 1][j]
                arr[i][j] += 0 if arr[i][j - 1] is None else arr[i][j - 1]
    return arr[-1][-1] % 1000000007

정확성  테스트
테스트 1 〉	통과 (0.01ms, 9.52MB)
테스트 2 〉	통과 (0.03ms, 9.59MB)
테스트 3 〉	통과 (0.04ms, 9.57MB)
테스트 4 〉	통과 (0.06ms, 9.51MB)
테스트 5 〉	통과 (0.13ms, 9.6MB)
테스트 6 〉	통과 (0.09ms, 9.45MB)
테스트 7 〉	통과 (0.09ms, 9.37MB)
테스트 8 〉	통과 (0.20ms, 9.62MB)
테스트 9 〉	통과 (0.10ms, 9.51MB)
테스트 10 〉	통과 (0.04ms, 9.62MB)
효율성  테스트
테스트 1 〉	통과 (5.59ms, 9.75MB)
테스트 2 〉	통과 (2.04ms, 9.55MB)
테스트 3 〉	통과 (2.44ms, 9.73MB)
테스트 4 〉	통과 (3.32ms, 9.75MB)
테스트 5 〉	통과 (2.86ms, 9.62MB)
테스트 6 〉	통과 (4.43ms, 9.76MB)
테스트 7 〉	통과 (2.42ms, 9.62MB)
테스트 8 〉	통과 (3.47ms, 9.84MB)
테스트 9 〉	통과 (3.59ms, 9.81MB)
테스트 10 〉	통과 (3.52ms, 9.59MB)

전형적인 동적계획법 문제입니다. 
경로를 담는 배열을 만들고, 배열에 경우의 수를 넣고, 합하면 됩니다.