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

문제 링크

---

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

접근 방법

---

 간략히 말하자면 2차원 배열 위에서 현재 값 보다 더 큰 값으로만 이동할 수 있을 때, 가장 멀리 이동 할 수 있는 거리를 구하는 문제이다. 단, 출발점이 정해져 있지 않아 모든 위치에서 출발을 시작 해 봐야 한다. 

 

 하지만, 동적계획법을 사용하여 많은 계산을 줄일 수 있다 어떻게 줄일 수 있을까?

아래의 그림을 보자!

예를 들어, 9에서 11로 이동한 경우와 5에서 11로 이동한 경우 모두 11에서 부터 끝 까지의 경우의 수는 같다는 것을 알 수 있다. 9 -> 11 -> 15 , 5 -> 11 -> 15, 즉 어떤 위치 부터 끝 까지의 값을 기록하면 중복되는 연산을 줄일 수 있다는 것이다.

 

dp[세로][가로]로 표현하여 기록할 수 있다.  

pair<int, int> nextdir[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

for (int i = 0; i < 4; i++) {
		int next_x = nowx + nextdir[i].first;
		int next_y = nowy + nextdir[i].second;
		if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
			if (map[nowx][nowy] < map[next_x][next_y]) {
				ret = max(ret, solve(next_x, next_y));
			}
		}
	}
dp += ret;
return dp;

가장 오래 살아남아야 하므로, 위의 코드를 보면 상,하,좌,우 4방향으로 이동했을 때 최댓값을 갱신하도록 하여, 현재의 생존일에 더하도록 하였다.   

소스 코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int map[500][500];
int dp[500][500];
pair<int, int> nextdir[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
int result = 0;
int n;

int solve(int nowx, int nowy) {

	int &ref = dp[nowx][nowy];
	int ret = 0;

	if (ref != 0)  //방문한 적이 있다면
		return ref;
	else  // 방문한적이 없다면
		ref = 1;

	for (int i = 0; i < 4; i++) {
		int next_x = nowx + nextdir[i].first;
		int next_y = nowy + nextdir[i].second;
		if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
			if (map[nowx][nowy] < map[next_x][next_y]) {
				ret = max(ret, solve(next_x, next_y));
			}
		}
	}
	ref += ret;
	return ref;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (dp[i][j] == 0) //방문 한적 없다면
				result = max(result, solve(i, j));
			else //방문한 적 있다면
				result = max(result, dp[i][j]);
		}

	cout << result << endl;
}