욕심쟁이 판다

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

Recursive DP로 풀 수 있는 문제였다.

머릿속에 DP 풀이는 떠오르는데, Iterative DP로 풀기에는 순서를 지정하기 애매할 때 Recursive DP를 고려하는 습관을 들이도록 하자.

CACHE 정의는 아래와 같이 했다.

• CACHE[i][j]: i행 j열에서 시작할 때 판다가 최대한 방문할 수 있는 지점의 수

점화식은 아래와 같다.

• CACHE[i][j] = max(1 + CACHE[ni][nj]) (단, ni행 nj열은 i행 j열에 인접하고, 이동 가능한 지점)

#include <iostream>
#include <vector>
#include <cstdint>
#include <algorithm>

using namespace std;

const int kMaxN = 500;

int N;
int WOODS[kMaxN][kMaxN];
int64_t CACHE[kMaxN][kMaxN];

bool IsSafe(const int row, const int col)
{
  if (0 > row || row >= N || 0 > col || col >= N)
  {
    return false;
  }

  return true;
}

int64_t Solve(const int row, const int col)
{
  int64_t& ret = CACHE[row][col];

  if (ret != -1)
  {
    return ret;
  }

  ret = 1;

  const int dr[4] = { -1, 0, 1, 0 };
  const int dc[4] = { 0, 1, 0, -1 };

  for (int d = 0; d < 4; ++d)
  {
    int nrow = row + dr[d];
    int ncol = col + dc[d];

    if (IsSafe(nrow, ncol) && WOODS[row][col] < WOODS[nrow][ncol])
    {
      ret = max(ret, 1 + Solve(nrow, ncol));
    }
  }

  return ret;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N;
  for (int r = 0; r < N; ++r)
  {
    for (int c = 0; c < N; ++c)
    {
      cin >> WOODS[r][c];
      CACHE[r][c] = -1;  ///< Initialize
    }
  }

  // Solve
  int64_t ans = -1;
  for (int r = 0; r < N; ++r)
  {
    for (int c = 0; c < N; ++c)
    {
      ans = max(ans, Solve(r, c));
    }
  }

  cout << ans << '\n';

  return 0;
}