[DP(Top-Down)]백준 1937 욕심쟁이 판다 C++

 

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

1937번: 욕심쟁이 판다

#include <iostream>
#include <vector>

using namespace std;

int n;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vector<int>> board;
vector<vector<int>> dp;

int func(int x, int y) {
    int& ret = dp[y][x];
    if (ret != -1) return ret;

    ret = 1;
    for(int i=0; i<4; i++) {
        int newX = x + dx[i];
        int newY = y + dy[i];
        if ((newX < 0) || (newY < 0) || (newX >= n) || (newY >= n)) continue;
        
        if (board[newY][newX] <= board[y][x]) continue;
        ret = max(ret, func(newX, newY) + 1);
    }
    
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    board.resize(n, vector<int>(n, 0));
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++)
            cin >> board[i][j];
    }

    dp.resize(n, vector<int>(n, -1));

    int answer = 1;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            answer = max(answer, func(i, j));
        }
    }
    cout << answer;

    return 0;
}