알고리즘
- save[0][0] = 1 부터 시작해서, 모든 점을 순서대로 방문하며 자신의 위, 왼쪽 점들 중 자신에게로 올 수 있는 모든 점들을 save[i][j]에 저장한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
typedef long long ll;
using namespace std;
int n, map[101][101];
ll save[101][101];
ll dp();
int main() {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
cout << dp();
}
ll dp() {
save[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int ki = i - 1; ki >= 0; ki--)
if (map[ki][j] == i - ki)
save[i][j] += save[ki][j];
for (int kj = j - 1; kj >= 0; kj--)
if (map[i][kj] == j - kj)
save[i][j] += save[i][kj];
}
}
return save[n - 1][n - 1];
}