1937

모든 경로를 탐색하려고 하면 경우의 수가 무척 많아져서 어렵다. 여기서는 문제의 조건을 잘 살펴야 한다.

- 판다는 상,하,좌,우 중 하나의 경로로 이동한다

- 대나무의 양은 증가하는 순서여야 한다.

위 두가지 조건만을 이용해서 dp를 만들어 줄 수 있다.

dp[x][y]는 어떤 위치(x,y)로 도달 할 때 판다가 최대 살 수 있는 일 수를 가지고 있다고 하자.

그럼 다음과 같은 점화식을 적용 할 수 있다.

dp[x][y] = (상하좌우에 있는 대나무중 현재 위치의 대나무보다 양이 작은 값들의 dp중 가장 큰 것) + 1

이해를 돕기 위해 그림으로 부연 설명을 하면..

파란색으로 칠해둔 위치의 dp값을 업데이트 하려고 한다. 이때 파란색 위치로 접근 할 수 있는 경로는 (x,y)위치의 상하좌우중 (x,y)의 위치보다 대나무 수가 적은 곳(상, 우)이다. 상, 우의 dp값중 가장 큰 값(2)에서 하루를 더 살 수 있는 것으로 (x,y)의 위치에 도달 할 때는 판다는 최대 3일을 살 수 있다.

위 알고리즘을 적용하려면 대나무의 수가 적은 순서대로 탐색을 해야한다. 그렇지 않으면 중간에 누락되는 경로가 생길 수 있다.

반드시 대나무가 증가하는 순서대로 진행되므로 circle이 생기지 않기 때문에 위 알고리즘 만으로 모든 경우를 포함 할 수 있다.

 
#include<cstdio>
#include<algorithm>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

using namespace std;

struct Node {
	int val, r, c;
};

int map[505][505];
int dp[505][505];

Node node[500 * 500];

int dr[4] = { 0, 1, 0, -1 };
int dc[4] = { 1, 0, -1, 0 };

bool compare(Node a, Node b) {
	if (a.val < b.val)
		return true;
	return false;
}

int main() {
	int N, i, j, nr;
	int r, c, val, ans;

	scanf("%d", &N);

	nr = 0;
	for (i = 1; i <= N; i++){
		for (j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
			node[nr].r = i;
			node[nr].c = j;
			node[nr++].val = map[i][j];
		}
	}

	sort(&node[0], &node[nr], compare);
	ans = 0;

	for (int i = 0; i < nr; i++) {
		r = node[i].r, c = node[i].c, val = node[i].val;

		dp[r][c] = 1;
		for (int j = 0; j < 4; j++) {
			if (map[r][c] > map[r + dr[j]][c + dc[j]]) {
				dp[r][c] = MAX(dp[r][c], dp[r + dr[j]][c + dc[j]] + 1);
				ans = MAX(ans, dp[r][c]);
			}
		}
	}

	printf("%d\n", ans);

	return 0;
}