이동하기

풀이

 메모이제이션을 위한 DP 테이블을 생성한 뒤, 맨 윗줄에서부터 배열을 훑어가며 DP 테이블에 값을 갱신하면된다. 점화식은 아래와 같다.

dp[i][j] = arr[i][j] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

import sys
N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

result = [[0]*M for _ in range(N)]

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

for x in range(N):
    for y in range(M):
        tem = [0]
        for i in range(3):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<N and 0<=ny<M:
                tem.append(graph[nx][ny])
        graph[x][y] += max(tem)
print(graph[x][y])

시간복잡도 : O(NM)