[백준] 1937-욕심쟁이 판다(C++)

문제링크:www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

내리막길 문제와 유사해서 크게 어렵지는 않았습니다.

예를 들어서, 단순히 오른쪽, 아래로만 이동하는게 아니라 위에 올라갔다가, 왼쪽으로 갔다가 올 수도 있기 때문에

모든경우를 탐색해주어야하는 이때, dp의 메모이제이션을 사용하는 식입니다.

dp의 UP-DOWN 방식으로 구현을 하자는 아이디어를 얻었습니다.

 

점화식은 아래처럼 구현했습니다. 이때 ny, nx는 인접한 4방향 좌표를 모두 탐색합니다.

if (ny >= 1 && ny <= n&&nx >= 1 && nx <= n)
			if (arr[y][x] < arr[ny][nx]) {
				ret = max(ret, solved(ny, nx) + 1);
		}

 

고민했던 부분은 모든 좌표에서 재귀함수를 호출하면 시간이 오래걸리지 않을까? 입니다.

근데 이때 dp는 초기화할 필요가 없기때문에 시간적으로 오래걸리지 않습니다.

dp[i][j]는 i,j 좌표에서 이동할 수 있는 최대값을 의미합니다.

 

 

아래는 전체 정답코드입니다.

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

int n = 0;
int arr[501][501] = { 0, };
int dp[501][501];
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
int result = 0;

int solved(int y, int x) {
	int &ret = dp[y][x];
	if (ret != -1) return ret;
	ret = 0;

	for (int i = 0; i < 4; i++) {
		int ny = y + y_ar[i];
		int nx = x + x_ar[i];
		if (ny >= 1 && ny <= n&&nx >= 1 && nx <= n)
			if (arr[y][x] < arr[ny][nx]) {
				ret = max(ret, solved(ny, nx) + 1);
		}

	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> arr[i][j];
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
				result = max(result, solved(i, j));
			
		}

	cout << result + 1 << endl;
	return 0;
}

dp라고 인식되는  순간 체감난이도가 확 줄었습니다.

이해가 안되시면 천천히 디버깅해보세요!