[BOJ] 백준 15924 욱제는 사과팬이야!!

문제 링크

https://www.acmicpc.net/problem/15924

구사과씨가 어디서 출발할지 모른다. 따라서 각각의 모든 점에서 X까지 갈 수 있는 경우의 수를 모두 구해서 더해야 한다. 역으로 X에서부터 시작해 뒤쪽에서 앞쪽으로 올 수 있는 경우의 수를 저장하자.

$d[i][j] = (i, j)$에서 X까지 갈 수 있는 경로의 수

$p[i][j] = $ 직사각형 지도에서 $(i, j)$의 정보 

$\left\{\begin{array}{c}d[i-1][j] = d[i-1][j] + d[i][j],\text{ if }\ i - 1 \geq 0 \text{ and } p[i-1][j] = \text{'S' or 'B'} \\ d[i][j-1] = d[i][j-1] + d[i][j],\text{ if }\ j - 1 \geq 0 \text{ and } p[i][j-1] = \text{'E' or 'B'} \end{array}\right. $

점화식을 세웠으니 반복문을 돌리자. 연산할때마다 $10^9+9$로 나눠주는 것을 잊으면 안된다.

정답 코드

질문, 피드백 환영합니다.