백준 10164. 격자상의 경로

tose33 2022. 6. 28. 14:39

10164번: 격자상의 경로

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으

www.acmicpc.net

경로의 경우의 수를 구하는 것도 대표적인 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