백준 1937 파이썬 python : 욕심쟁이 판다 @@황소처럼 우직하게@@ dp는 썻던걸 또 써먹는 알고리즘입니다.

dp 는 썻던걸 또 써먹어야됩니다.

그걸 어떻게 써먹을지 고민해야됩니다.

dp 각 칸에 거기서 시작했을 때의 최대값을 구하고,

좌우를 살피는데 더 큰 곳만 살피는데, 거기에 값이 있다면 본인 좌표에는 그 값 + 1 을 넣으면되는 거죠

근데 네 방향이니까 네 방향중에 max 값을 넣어야겠죠

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n = int(input())
mat = []
for i in range(n):
    mat.append(list(map(int, input().split())))

dp = [[-1 for _ in range(n)] for _ in range(n)]

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

def dfs(sy, sx):
    # print('---------')
    # for s in dp:
    #     print(s)
    dp[sy][sx] = 0
    lst = []
    for i in range(4):
        ny = sy + dy[i]
        nx = sx + dx[i]
        if 0 <= nx < n and 0 <= ny < n:
            if mat[sy][sx] < mat[ny][nx]:
                if dp[ny][nx] == -1:
                    dfs(ny, nx)
                lst.append(dp[ny][nx])
    if lst:
        dp[sy][sx] = max(lst) + 1
    else:
        dp[sy][sx] = 1

ans = 0
for i in range(n):
    for j in range(n):
        if dp[i][j] == -1:
            dfs(i, j)
for s in dp:
    ans = max(ans, max(s))
print(ans)