[알고리즘] 백준 - 욕심쟁이 판다

백준 - 욕심쟁이 판다

다른 사람 풀이

import sys, copy
from collections import deque

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

max_ans = -sys.maxsize

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

# dp[i][j] = (i,j)에서 갈 수 있는 루트 중 제일 길게 갈 수 있는 루트 길이
dp = [[-1]*n for _ in range(n)]


def dfs(y, x):
    if dp[y][x] != -1:
        return dp[y][x]

    dp[y][x] = 1

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            if graph[ny][nx] > graph[y][x]:
                dp[y][x] = max(dp[y][x], dfs(ny, nx)+1)

    return dp[y][x]

for i in range(n):
    for j in range(n):
        max_ans = max(max_ans, dfs(i, j))

print(max_ans)

그냥 DFS를 다 돌리면 시간 초과가 난다.
이번에도 역시 점화식이 중요했는데, dp[i][j]를 (i,j)에서 출발해서 갈 수 있는 루트 중 가장 긴 루트의 길이라고 하자. 그러면 이미 dp[i][j]는 최적해라는 것이 보장되었기 때문에, 다른 지점에서 길을 찾다가 (i,j)에 도착하면 dp[i][j]를 그대로 쓰면 된다.