[BAE/<JOON> 문제풀이] 1937. 욕심쟁이 판다 (DP.036)

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

1937번: 욕심쟁이 판다

내리막길과 거의 같은 문제라서 수월하게 풀 수 있었던 것 같다.

 

문제의 요점은 깊이우선 탐색으로 발생하는 중복 탐색을 어떻게 효율적으로 줄이느냐 이다.

 

dp[x][y]를 x, y지점에서 판다가 살아 남을 수 있는 최대 일수로 지정하면

 

탐색의 최저점을 찍고 다시 올라 올 때 현재 지점에서 살아남을 수 있는 최대 일 수는 

 

최저점에서의 일 수 - 현재 지점까지 살아남은 일 수 이다.

 

#include <iostream>
#include <vector>

using namespace std;

int mvx[5] = { 0, -1, 0, 1, 0 };
int mvy[5] = { 0, 0, -1, 0, 1 };
vector<vector<int>> arr, dp;
int n;

int maxx = -1;

int r(int x, int y, int c) {
    dp[x][y] = c;    
    int ret = c;
    for (int i = 1; i <= 4; i++) {
        int mx = x + mvx[i];
        int my = y + mvy[i];
        if (mx > n || mx < 1 || my > n || my < 1 || arr[mx][my] <= arr[x][y]) continue;        
        if (dp[mx][my] != -1) {
            ret = ret > dp[mx][my] + c + 1 ? ret : dp[mx][my] + c + 1;            
            continue;
        }
        int res = r(mx, my, c + 1);
        ret = ret > res ? ret : res;
    }
    if (maxx < ret) maxx = ret;
    dp[x][y] = ret - c;
    return ret;
}

int main()
{
    cin >> n;
    arr.resize(n + 1);
    dp.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i].resize(n + 1);
        arr[i].resize(n + 1);
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = -1;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {            
            r(i, j, 1);
        }
    }

    /*for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/

    cout << maxx << endl;

    return 0;
}