백준 / 1937 욕심쟁이 판다 C++

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

판다가 주어진 대나무 맵에서 전날 먹은 대나무 양보다 많이 먹는 쪽으로만 이동할 때 며칠동안 살아남을 수 있는지 구하는 문제입니다.

 

처음에는 dfs만 가지고 구했는데 시간초과도 아니고 그냥 틀렸다 그래서 당황스러웠습니다. (아무리 생각해도 반례는 떠오르지 않았다....) 

 

그렇기에 dp를 조금 첨가하여 풀었습니다. dp[y][x]를 (y,x)에서 최대로 이동할 수 있는 칸의 수라고 합시다.

처음에 dp[y][x]는 0으로 초기화한 뒤, dp[y][x]가 0이 아니면 해당 지점은 최대 이동 칸 수를 알고 있는 경우이므로 return을 합니다.

0인 경우는 dfs를 돌려 조건에 맞는 경우, dp[y][x] = max(dp[y][x], dfs(nx, ny)+1) 임을 이용하면 됩니다. 그리고 dp[y][x]를 return 합니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

void make_map()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dp[i][j] = 0;
		}
	}
}

int dfs(int x, int y)
{
	if (dp[y][x] != 0)
		return dp[y][x];
	
	dp[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
			if (map[y][x] < map[ny][nx]) {
				dp[y][x] = max(dp[y][x], dfs(nx, ny) + 1);
			}
		}
	}
	return dp[y][x];
}

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

	make_map();
	int result = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			result = max(result, dfs(j, i));
		}
	}
	cout << result;
}