(BOJ 1937 욕심쟁이 판다) Bottom-up → Top-down DP

[풀이]

Sol 1) 매 칸마다 DFS 돌리기
Sol 2) 
dp[i][j] : i,j가 끝나는 점일때 판다가 생존한 기간
이라고 정의할 때, dp[i][j]는 주변 dp값으로 정의 가능함

dp[i][j] = max(board[x][y] 숫자보다 작은 주변의 dp값) + 1
만약 주변 값이 다 현재보다 크다면, dp[i][j] = 1

핵심은, Bottom-up식 풀이는 초기화를 어떻게 해야할 지 모르겠다는 것. 
→ Top-down으로 시작하면, 주변 좌표 [xn][yn]에 DP 재귀함수를 부르면 됨
(이 형태가 마치 DFS처럼 파고든다고 해서, 문제 분류가 DFS로 된 듯)


[생각/구현 어려웠던 부분]
문제 분류(DFS)를 먼저 봐서, 'DFS를 어떻게 써야하지?'라는 편견에 빠짐.

 

DP 정의 자체 (Optimal substructure) 에 집중하면 답이 보인다

dp[i][j]가 하위문제로 어떻게 정의되지?

→ Bottom-up 방식은 초기화 할 수가 없네

→ 그럼 정의가 안된 주변 dp[xn][yn]에도 DP함수 재귀호출해서 값 구하면 되잖아 

→ AC

* Python은 재귀 depth 에러남 -> C++로 이식

#include <bits/stdc++.h>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define FOReq(i, m, n) for(int i = (m); i <= (n); ++i)
#define all(c) (c).begin(), (c).end()
using namespace std;

#define X first
#define Y second

using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using pii = pair<int, int>;
using tup = tuple<int, int, int>;
using ll = long long;
const int INF = 1e9;

const int SIZ = 500;
int board[SIZ][SIZ];
int dp[SIZ][SIZ];
int N;

inline bool boundary_0(int x, int y) { return 0 <= x && x < N && 0 <= y && y < N; };

int DP(int x, int y) {
    // Memoization
    if (dp[x][y] != -1)
        return dp[x][y];

    dp[x][y] = 1; // init
    FOR(d, 0, 4) {
        int xn = x + "1210"[d] - '1'; // E S W N
        int yn = y + "2101"[d] - '1';
        if (!boundary_0(xn, yn) || board[xn][yn] >= board[x][y]) continue;
        if (dp[xn][yn] == -1)
            dp[xn][yn] = DP(xn, yn); // 주변 dp가 정의 안되어있으면 재귀호출

        dp[x][y] = max(dp[x][y], dp[xn][yn] + 1); // memo
    }
    return dp[x][y];
}


int main()
{
#ifdef DBG
    freopen("../input.txt", "r", stdin);
#endif
    fastio;

    cin >> N;
    FOR(x, 0, N) FOR(y, 0, N) cin >> board[x][y];
    memset(dp, -1, sizeof(dp));

    int max_day = 0;
    FOR(x, 0, N) FOR(y, 0, N) {
        max_day = max(max_day, DP(x, y));
    }
    cout << max_day;
}