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

1937번: 욕심쟁이 판다

---

 

풀이

평범하게 모든타일에서 시작해서 탐색하면 시간초과에 걸린다.

메모이제이션을 이용하면 쉽게 통과할 수 있다.

 

 

코드

#include <bits/stdc++.h>

using namespace std;

int board[501][501];
int dp[501][501];

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int answer = 0;
int n;
bool InMap(int x, int y){
    if( 0 <= x && x < n&& 0<=y && y < n)
    return true;
    return false;
}
int DFS(int x,int y, int c){
    if(dp[y][x] != 100000)
    return dp[y][x];
    
    dp[y][x] = 1;
    int hegiht = board[y][x];
    int count = 0;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny= y + dy[i];
        int nHeight= board[ny][nx];
        if(InMap(nx,ny) && hegiht < nHeight){
            count = max(count,DFS(nx,ny,c+1));
        }
    }
    dp[y][x] += count;
    return dp[y][x];
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    priority_queue<pair<int,int>> q;
    for(int y =0; y < n; y++){
        for(int x = 0; x <n;x++){
            cin >> board[y][x];
            dp[y][x] = 100000;
        }
    }
    for(int y =0; y < n; y++){
        for(int x = 0; x <n;x++){
            if(dp[y][x] == 100000)
            answer = max(answer,DFS(x,y,1));
        }
    }
    cout << answer;
    return 0;
}