욕심쟁이 판다 - 1937

//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;
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

 

 

 

 

 

욕심쟁이 판다

DP문제 입니다. 더 큰쪽으로만 향하기 때문에 싸이클이 생기지 않습니다.