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

 

다이나믹 프로그래밍 문제입니다.

 

n*n의 배열에서 가장 긴 증가하는 수열을 구하는 문제입니다.

수열은 상하좌우로 연결될 수 있습니다.

 

재귀함수로 문제를 풀었습니다.

모든 좌표를 전부 검사합니다.

 

재귀함수에 좌표를 넣고

현재 좌표에서 상하좌우 중 큰값이 있다면

그 위치에서 다시 재귀함수를 들어갑니다.

현재 위치 값을 저장하고 리턴합니다.

 

이렇게 상하좌우를 전부 검색하여 나온 값 중

가장 큰 값이 현재 위치의 값이 됩니다.

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

int map[510][510];
int DP[510][510];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };

int search(int i, int j) 
{
	int maxNum = 0;
	if (DP[i][j] != 1) {
		return DP[i][j];
	}
	for (int k = 0; k < 4; ++k) {
		int x = i - moveX[k];
		int y = j - moveY[k];
		if (map[i][j] < map[x][y]) {
			maxNum = max(maxNum, search(x,y));
		}
	}
	DP[i][j] += maxNum;

	return DP[i][j];
}

int main(int argc, char *argv[])
{
	int maxNum = 0;
	int n;
	cin >> n;

	for (int i = 0; i <= n + 1; ++i) {
		for (int j = 0; j <= n + 1; ++j) {
			map[i][j] = 0;
			DP[i][j] = 1;
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cin >> map[i][j];
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			search(i, j);
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			maxNum = max(maxNum, DP[i][j]);
		}
	}
	cout << maxNum << endl;

	return 0;
}