Algorithm/BOJ
욕심쟁이 판다 - 1937
jhg0406
2020. 2. 25. 20:18
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
//1937 - 욕심쟁이 판다
#include <iostream>
#include <vector>
using namespace std;
#define IMP -100000000
int N;
vector<vector<int>> arr;
vector<vector<int>> cache;
int xarr[4] = {1, -1, 0, 0};
int yarr[4] = {0, 0, 1, -1};
void init()
{
cin >> N;
arr = cache = vector<vector<int>>(N+2, vector<int>(N+2));
for(int i = 1; i<=N; ++i)
for(int j = 1; j<=N; ++j)
{
cin >> arr[i][j];
cache[i][j] = -1;
}
for(int i = 0; i<N+2; ++i)
arr[0][i] = arr[i][0] = arr[N+1][i] = arr[i][N+1] = -1;
}
int dp(int x, int y)
{
int& ret = cache[x][y];
if(ret != -1)
return ret;
ret = 0;
for(int i = 0; i<4; ++i)
if(arr[x][y] < arr[x+xarr[i]][y+yarr[i]])
ret = max(ret, dp(x+xarr[i], y+yarr[i]));
return ++ret;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
init();
int ans = IMP;
for(int i = 1; i<=N; ++i)
for(int j = 1; j<=N; ++j)
ans = max(ans, dp(i, j));
cout << ans;
}
|
cs |
https://www.acmicpc.net/problem/1937
1937번: 욕심쟁이 판다
n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이
www.acmicpc.net
욕심쟁이 판다
DP문제 입니다. 더 큰쪽으로만 향하기 때문에 싸이클이 생기지 않습니다.
