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

문제 링크: https://www.acmicpc.net/problem/1937

문제

입출력

문제 접근

dp문제이다. 그리고 한 방향으로 연결된 트리 문제이다.
dp로 푸는 거라고 인지를 한다면 금방 풀 수 있는 문제이다. 단방향으로 연결되어 있고, tree기 때문에 cycle도 존재하지 않아, 쉽게 풀 수 있다. 상하좌우중 자기가 갈 수 있는 곳 중에서 +1을 더해주면, 현재 위치에서 가장 오래 살 수 있는 기간이 나온다.

코드 구현(c++)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int map[501][501];
int cache[501][501];
int n;
int xMove[4] = {0,0,1,-1};
int yMove[4] = {1,-1,0,0};
int dp(int y, int x){
    int& res = cache[y][x];
    if(res != -1) return res;
    res = 1;
    for(int i = 0 ; i < 4 ; i++){
        int nextX = x + xMove[i]; int nextY = y + yMove[i];
        if(nextX >= n || nextX < 0 || nextY >= n || nextY < 0 || map[y][x] >= map[nextY][nextX]) continue;
        res = max(res, dp(nextY, nextX) + 1);
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;

    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            cin >> map[i][j];
        }
    }
    int result = -1;
    memset(cache, -1, sizeof(cache));
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            result = max(result, dp(i,j));
        }
    }
    cout << result << "\n";
}