등굣길

import sys; sys.setrecursionlimit(100000) cache = {(0, 0): 1} def solve(r, c, R, C, puddles): if (r, c) in cache: return cache[(r, c)] # 왼쪽 아니면 위쪽에서 옵니다. # 단, puddle이 아니어야 합니다. v = 0 for dr, dc in [(-1, 0), (0, -1)]: if (r+dr, c+dc) not in puddles and 0 <= r+dr < R and 0 <= c+dc < C: v += solve(r+dr, c+dc, R, C, puddles) cache[(r, c)] = v % 1000000007 return cache[(r, c)] def solution(m, n, puddles): # DP로 해결 puddles = set((r-1, c-1) for c, r in puddles) return solve(n-1, m-1, n, m, puddles)