백준 1937 - 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

 

다음 dp 테이블을 세운다.

 

dp[i][j] := 좌표 (i, j)에서 시작했을 때 가질 수 있는 최장 경로의 길이

 

각 좌표마다 가질 수 있는 최장 경로를 DFS로 검색하면 $O(V^{2}E)$가 되어 시간 초과를 받게 된다.

 

이를 $O(V^{2})$로 줄여보자.

 

각 정점마다 DFS를 수행하면서 거쳐간 정점에 저장한 지역 최장 경로는 일단 저장한다.

 

그리고 이미 거쳐간 정점에 대해서는 DFS를 시작하지 않도록 한다.

 

거쳐갔다는 것은 이미 어떤 두 정점 사이의 경유점이라는 뜻이기 때문에 최장 경로의 시작점이 될 수 없다.

 

지나간 적이 없는 정점에 대해 DFS를 시작할 때 다음으로 가는 정점에 지역 최장 경로 값이 존재한다면 이 값을 더하고 DFS를 종료하면 된다. 해당 정점은 이미 지역 최장 경로를 가지고 있기 때문에 중복해서 탐색할 필요가 없기 때문이다.

 

이렇게 중복되는 검색을 제거하면 $O(V^{2})$의 시간 복잡도로 모든 정점에서 가질 수 있는 최장 경로를 구할 수 있게 되어 그 값을 출력하면 된다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int n;
int mesh[500][500];
int dp[500][500];
int ans;

int memo(int r, int c)
{
  int &ret = dp[r][c];

  if (ret != -1) return ret;

  ret = 1;

  for (int i = 0; i < 4; ++i)
  {
    int nr = r + ("2213"[i] - '2');
    int nc = c + ("1322"[i] - '2');

    if (nr < 0 || nc < 0 || nr >= n || nc >= n || mesh[nr][nc] <= mesh[r][c]) continue;

    ret = max(ret, memo(nr, nc) + 1);
  }

  return ret;
}

void solve()
{
  memset(dp, -1, sizeof dp);
  cin >> n;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      cin >> mesh[i][j];
  
  int ans = 0;

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      ans = max(ans, memo(i, j));

  cout << ans;
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}