์•Œ๊ณ ๋ฆฌ์ฆ˜

  • save[0][0] = 1 ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ, ๋ชจ๋“  ์ ์„ ์ˆœ์„œ๋Œ€๋กœ ๋ฐฉ๋ฌธํ•˜๋ฉฐ ์ž์‹ ์˜ ์œ„, ์™ผ์ชฝ ์ ๋“ค ์ค‘ ์ž์‹ ์—๊ฒŒ๋กœ ์˜ฌ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์ ๋“ค์„ save[i][j]์— ์ €์žฅํ•œ๋‹ค.

์ฝ”๋“œ

#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];
}