7297 : 메모이제이션 격자
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times M$ 격자에서 좌상단 $(0, 0)$에서 우하단 $(N-1, M-1)$까지 오른쪽 또는 아래쪽으로만 이동하는 경로의 수를 구하십시오.
장애물(1)이 있는 셀은 지날 수 없습니다.
메모이제이션으로 중복 계산을 방지합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
장애물(1)이 있는 셀은 지날 수 없습니다.
메모이제이션으로 중복 계산을 방지합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 격자의 크기 $N$, $M$이 주어집니다. ($1 \le N, M \le 100$)
둘째 줄부터 $N$개의 줄에 격자 정보가 주어집니다. (0: 이동 가능, 1: 장애물)
둘째 줄부터 $N$개의 줄에 격자 정보가 주어집니다. (0: 이동 가능, 1: 장애물)
출력 설명
좌상단에서 우하단까지 갈 수 있는 경로의 수를 $10^9+7$로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 0 0
0 1 0
0 0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
@lru_cache(maxsize=None); def dp(i,j): if grid[i][j]==1: return 0; if i==0 and j==0: return 1; return ((dp(i-1,j) if i>0 else 0)+(dp(i,j-1) if j>0 else 0))%MOD