[백준] 21923 곡예 비행 Python - DP

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

21923번: 곡예 비행

상승비행의 dp와 하강 비행의 dp값을 각각 구한 후, 

두 테이블을 합쳐서 나오는 최댓값을 구한다. 

n, m = map(int, input().split())
array = []
for i in range(n):
    data = list(map(int, input().split()))
    array.append(data)

up = [(0, -1), (1, 0)]
down = [(1,0), (0,1)] 

dp_up = [[-1e9] * m for _ in range(n)]  # array[i][j] 값이 음수일수도 있음 
dp_down = [[-1e9] * m for _ in range(n)]

dp_up[n-1][0] = array[n-1][0]
dp_down[n-1][m-1] = array[n-1][m-1] 
# 상승 
for x in range(n-1, -1, -1):
    for y in range(0, m):
        for d in up: # 상승의 경우 - 자기 자신 기준 왼쪽에서 오거나 아래쪽에서 오는 경우 중 MAX 값 저장 
            nx = x + d[0]
            ny = y + d[1]
            if 0 <= nx < n and 0 <= ny < m:             
                dp_up[x][y] = max(dp_up[x][y], dp_up[nx][ny] + array[x][y])
# 하강 
for x in range(n-1, -1, -1):
    for y in range(m-1, -1, -1):
        for d in down: # 하강의 경우 - 자기자신 기준 오른쪽에서 오거나 위쪽에서 오는 경우
            nx = x + d[0]
            ny = y + d[1]
            if 0 <= nx < n and 0 <= ny < m:             
                dp_down[x][y] = max(dp_down[x][y], dp_down[nx][ny] + array[x][y])

#상승 + 하강 
answer = -1e9
for i in range(n):
    for j in range(m):
        answer = max(answer, dp_up[i][j] + dp_down[i][j])
print(answer)