코딩테스트 고득점 Kit - 동적계획법(Dynamic Programming) 3 (Level 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from itertools import product

def solution(m, n, puddles):
    w, h = n, m

    m = [[0]*(h+1) for _ in range(w+1)]
    for y, x in puddles:
        m[x][y] = -1
    m[1][1] = 1

    for i, j in product(range(1, w+1), range(1, h+1)):
        if i == j == 1 or m[i][j] == -1:
            continue

        up   = max(m[i-1][j], 0)
        left = max(m[i][j-1], 0)
        m[i][j] = up + left

    return m[-1][-1] % 1000000007