백준 1937번: 욕심쟁이 판다

[문제 링크]

1937번: 욕심쟁이 판다

---

https://onlytrying.tistory.com/104 점프 문제와 유사한 유형의 문제였다.

 

(y,x) 좌표에서 판다가 생존할 수 있는 일수는 항상 같기 때문에 이를 메모이제이션 해주면 중복 탐색을 최소화하게 되어 빠르게 정답을 구할 수 있다.

---

#include <iostream>
using namespace std;

int N, map[501][501], memo[501][501];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

int max(int a, int b) { return a > b ? a : b; }

int Topdown(int startY, int startX)
{
	int& ret = memo[startY][startX];
	if (ret != 0) return ret;

	ret = 1;

	for (int i = 0; i < 4; i++)
	{
		int nextY = startY + dy[i];
		int nextX = startX + dx[i];
		if (nextY <= N && nextX <= N && map[startY][startX] < map[nextY][nextX])
			ret = max(ret, Topdown(nextY, nextX) + 1);
	}

	return ret;
}

int main(void)
{
	cin >> N;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];

	int res = 1;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			res = max(res, Topdown(i, j));

	cout << res << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 92 day