M x N 크기의 양의 정수 매트릭스와 비용(cost)가 주어졌을 때, 주어진 비용으로 매트릭스의 시작 위치 (0, 0)에서 마지막 위치 (M-1, N-1)까지 도달하는 경로의 수를 구하시오.
매트릭스에서 이동한 경로의 비용은 거쳐간 셀 값의 합이다.
매트릭스에서는 오직 오른쪽 한 칸 또는 아래쪽 한 칸으로만 이동할 수 있다.
즉, 셀 (i, j)에서는 (i, j+1) 또는 (i+1, j)로 이동할 수 있다.
- Input
[[4, 7, 1, 6],
[5, 7, 3, 9],
[3, 2, 1, 2],
[7, 1, 6, 3]]
cost = 25
- Output : 2 (두 가지 경로는 4-7-1-3-1-6-3, 4-5-7-3-1-2-3)