백준 1937 : 욕심쟁이 판다 c++

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

풀이

1. 일단 기본적으로는 완전 탐색이지만

2. 만약 0이 아닌 값이 들어있으면 바로 리턴하는 DP방식!

3. 주위에 자기 값보다 큰 대나무 값이 있으면 '그 좌표의 DP 값 +1' 과 현재 '자기 DP 값' 비교!!

 

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

int n;
int map[501][501];
int dp[501][501] = { 0, };
int answer = 0;

int d_r[4] = { 1,-1,0,0 };
int d_c[4] = { 0,0,1,-1 };

int DP(int r, int c)
{
	if (dp[r][c] != 0)//이미 지정 했으면 
		return dp[r][c];

	dp[r][c] = 1; // 처음으로 1 지정!

	for (int i = 0; i < 4; i++)
	{
		int new_r = r + d_r[i];
		int new_c = c + d_c[i];
		if (new_r < n && new_r >=0 && new_c <n && new_c >= 0)//이동할 곳이 지도 안이라면!!
		{
			if (map[new_r][new_c] > map[r][c])//새 좌표가 대나무가 더 많아야 이동 가능!!
			{
				dp[r][c] = max(dp[r][c], DP(new_r, new_c) + 1);
			}
		}
	}

	return dp[r][c];
}



int main()
{
	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++)
		{
			answer = max(answer,DP(i, j));

		}

	cout << answer<<endl;
	return 0;

}

 

 

 

 

후기

1. 이거도 내가 맨날 고생하는 DFS BFS 처럼 생겼지만 런타임 에러떠서 DP로 풀어야되는 문제다!

2. 이번에도 역시나 구글링했다!!

3. 하지만 쫌 자신감 생겼다 ㅎㅎ