728x90

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

 

1937번: 욕심쟁이 판다

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이

www.acmicpc.net

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> v;
vector<vector<int>> dp;
int n;

int dfs(int i, int j) {
	bool flag = false;
	if (dp[i][j] != 0) return dp[i][j];
	int maximum = 0;
	if (i + 1 < n && v[i][j] < v[i + 1][j]) {
		int temp = 1 + dfs(i + 1, j);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (i - 1 >= 0 && v[i][j] < v[i - 1][j]) {
		int temp = 1 + dfs(i - 1, j);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (j + 1 < n && v[i][j] < v[i][j + 1]) {
		int temp = 1 + dfs(i, j + 1);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (j - 1 >= 0 && v[i][j] < v[i][j - 1]) {
		int temp = 1 + dfs(i, j - 1);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (!flag) {
		dp[i][j] = 1;
	}
	return dp[i][j];
}

int main() {
	cin >> n;
	v = vector<vector<int>>(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	int maxDp = 0;
	dp = vector<vector<int>>(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dfs(i, j);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dp[i][j] > maxDp) maxDp = dp[i][j];
		}
	}
	cout << maxDp;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2631번 줄세우기  (0) 2020.03.15
[백준] 9084번 동전  (0) 2020.03.14
[백준] 3036번 링  (0) 2020.03.13
[백준] 5338번 마이크로소프트 로고  (0) 2020.03.13
[백준] 1699번 제곱수의 합  (0) 2020.03.13

+ Recent posts