[백준/BOJ] 백준 1520번 : 내리막 길

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

cache를 사용해 해당 위치에서 값을 구한 적이 있을 때 다시 계산하지 않고 그 값을 리턴했다

 

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int m, n;
int board[500][500];
int cache[500][500];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int Solve(pair<int, int> here)
{
	//오른쪽 아래칸에 도착했을때
	if (here.first == m - 1 && here.second == n - 1)
		return 1;

	int& ret = cache[here.first][here.second];

	//계산한적이 있을때
	if (ret != -1)
		return ret;

	ret = 0;

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		//there에 갈 수 있는지 확인
		if (there.first >= 0 && there.first < m && there.second >= 0 && there.second < n && board[here.first][here.second] > board[there.first][there.second])
			ret += Solve(there);
	}

	return ret;
}

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

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

	int input;

	cin >> m >> n;

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

	//왼쪽 위칸에서 시작
	pair<int, int> start = make_pair(0, 0);

	cout << Solve(start);

	return 0;
}