욕심쟁이 판다 C++ - 백준 1937

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

내리막 길과 굉장히 유사한 문제.

내리막 길 문제를 푼지 어언 3달이 되어 잊어버려서, 대충 dfs로 접근했는데 TLE났다.

문제 접근

$(i,j)$칸이 칸의 길이가 더 추가될 여지가 있는 칸이면 그 칸의 $DP$값을

확정시키지 않고 인접한 4칸 중에 최댓값으로 갱신한다.

예를 들면 다음과 같다.

길이가 갱신될 여지가 있는 칸(빨간색으로 동그라미 친)은 더 큰 수가

인접해 있어 더 큰 수 칸으로 dfs를 수행해준다.

만약 어떤 칸이 어떤 큰 수와도 인접해 있지 않다면 1을 리턴하게 했다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n,dp[500][500],arr[500][500],ans=1,dx[]={1,-1,0,0},dy[]={0,0,1,-1};

int solve(int x, int y){
    if(dp[x][y]!=-1) return dp[x][y];
    bool b=0;
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(n<=nx || nx<0 || n<=ny || ny<0) continue;
        if(arr[nx][ny]>arr[x][y]){dp[x][y]=max(dp[x][y],solve(nx,ny)+1);b=1;}
    }
    if(!b) return 1;
    else return dp[x][y];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    memset(dp,-1,sizeof(dp));
    cin >> n;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin >> arr[i][j];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++){dp[i][j]=solve(i,j);ans=max(ans,dp[i][j]);}
    cout << ans;
    return 0;
}