[DP] 격자 경로의 수

시간 제한: 1000 ms메모리 제한: 256 MBSilver V3작성자: 관리자

문제

$R \times C$ 격자가 있다. 각 칸은 빈칸( $0$ ) 또는 막힌 칸( $1$ )이다. 왼쪽 위 $(0, 0)$ 에서 출발해 오른쪽 또는 아래로만 한 칸씩 움직여 오른쪽 아래 에 닿는 경로의 수를 구하라. 막힌 칸은 지날 수 없다. 답이 클 수 있으니 로 나눈 나머지를 출력한다. 시작이나 도착 칸이 막혀 있으면 이다.

문제 통계

0

전체 제출

0

정답

0.0%

정답률

0

정답자 수

)

(R-1, C-1)

1{,}000{,}000{,}007

0

접근

$dp[i][j]$ 를 " $(0,0)$ 에서 $(i, j)$ 까지 오는 경로의 수"라 하면 위와 왼쪽에서만 올 수 있다.

$dp[i][j] = dp[i-1][j] + dp[i][j-1]$

막힌 칸은 $dp = 0$ 으로 두고 건너뛴다.

입력

첫 줄에 $R$ 과 $C$ ( $1 \le R, C \le 1000$ ). 다음 $R$ 줄에 각 줄 $C$ 개의 $0$ 또는 $1$ .

출력

경로의 수를 $1{,}000{,}000{,}007$ 로 나눈 나머지.

입출력 예시