[PS] 학교 가는 길

Programmers: 학교 가는 길

Conditions

• 집에서 학교까지 가는 길은 $m \times n$ 크기의 격자 모양으로 나타낼 수 있음.
• $m$, $n$은 1 이상 100 이하인 자연수. $m$, $n$이 모두 1인 경우는 입력으로 주어지지 않음.
• 집의 좌표는 $(1, 1)$, 학교의 좌표는 $(m, n)$.
• 물에 잠긴 지역인 puddles의 좌표는 0개 이상 10개 이하.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않음.
• 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 반환.

Design

• 해당 지점까지 올 수 있는 경로의 개수를 이차원 배열로 나타냄.
• $m_{ij}$가 puddle이면 그 지점은 갈 수 없음.
• $m_{(i-1)j}$이 puddle이면 $m_{ij} = m_{i(j-1)}$, vice versa.
• 둘 다 puddle이 아니라면 $m_{ij} = m_{(i-1)j} + m_{i(j-1)}$.

Recursive equation

Implementation