백준 10164. 격자상의 경로

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

10164번: 격자상의 경로

 

경로의 경우의 수를 구하는 것도 대표적인 dp 문제 중 하나다.

 

로봇이 오른쪽 or 아래로 이동 할 수 있으므로 d[r][c]가 [r][c]에 도달할수 있는 경로의 수라고 할때, d[r][c] = d[r-1][c] + d[r][c-1] 이다. 

물론 가장 첫 행과 열은 모두 1이다. (직선으로 이동할수 밖에 없다) 

 

이 문제는 중간에 지점 하나를 무조건 거쳐가야 하는 경우가 있는데, 해당 좌표까지의 경로의수 x 해당 좌표에서 부터 도착지까지의 경로의 수가 답이다. 

 

그냥 첫 지점부터 무조건 거쳐가야 하는 지점을 따로 때서 보고, 무조건 거쳐가야 하는 지점부터 도착지점 까지를 때서 보면 쉽다.

 

위와 같이 주어졌다면 

첫 지점부터 무조건 거쳐가야 하는 지점:

1	2	3
6	7	8

 

무조건 거쳐가야 하는 지점부터 도착지점 까지:

8	9	10
13	14	15