어떤 알고리즘?

• 경우의 수를 구하는 문제이다.
  -> 바로 탑다운을 생각했고,

• 문제를 분석해보면, 이렇게도 갈수 있는거 아닌가? 했는데,
  아래의 3개 뿐이므로, 이동하려고하는 point뿐아니라, dir해당하는 모든 값을 확인하는 거라고 확정함.
  => 상하좌우 한칸씩 나아가는 방법으로 해서 조건 처리해서 안되면, 더이상 진입 안하게 함.

문제 해결 전략

• 상하좌우로 한칸씩 가면서 이동가능하면 더 들어가는 조건식을 작성함.

• 그러다가 맨오른쪽 아래 칸 만나면 1, 성공을 반환함.

• 위의 조건처리로 이동못하면 안가게 함으로써 실패 조건 작성안했다.

• 그리고 중복은 발생할 수 없는 구조다. : 백트래킹 아니므로,

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
using namespace std;

int m, n;

int memo[501][501];
int v[501][501];

int go(int y, int x)
{
	if (y == m - 1 && x == n - 1)
		return 1;

	int& ret = memo[y][x];
	
	if (ret != -1)
		return ret;

	ret = 0;
	if (y - 1 >= 0 && v[y][x] > v[y - 1][x])
		ret += go(y - 1, x);

	if(y + 1 < m && v[y][x] > v[y + 1][x])
		ret += go(y + 1, x);

	if (x - 1 >= 0 && v[y][x] > v[y][x - 1])
		ret += go(y , x - 1);

	if (x + 1 < n && v[y][x] > v[y][x + 1])
		ret += go(y, x + 1);

	return ret;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	
	// 이동경로의 개수 
	// 위로 올라가도 된다.
	
	// 중복은 없다. 

	// 이동하려는 point만 보는 것이 아니라, 
	// 가는 지점에 있는 값들이 다 작아야만 가능한거 같다. 

	// 갈수 있냐 없냐 에 대한 경로수이므로
	// 경우의 수???

	// 내생각에는 한칸씩 가게 해서 못가면 
	// 그냥 0으로 하게 하는 것이 맞을 듯 하다.

	cin >> m >> n;

	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> v[i][j];
		}
	}

	memset(memo, -1, sizeof(memo));

	cout << go(0, 0);
}