문제

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

시행착오

from collections import deque
n,m=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]

dx=[1,0,1]
dy=[0,1,1]
q=deque()

q.append((0,0,board[0][0]))
answer=0
while q:
    a,b,d = q.popleft()

    if a==n-1 and b==m-1:
        answer=max(answer,d)
        continue
    for i in range(3):
        na=a+dx[i]
        nb=b+dy[i]
        if 0<=na<n and 0<=nb<m:
            q.append((na,nb,d+board[na][nb]))

print(answer)

맨처음에는 큐를 이용하여서 하나씩 탐색하여 최대값을 구해나갈려고 했으나, 메모리초과가 났다.

코드

n,m=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(m+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j]=board[i-1][j-1]+max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])


print(dp[n][m])

이런 식으로 입력을 받을 경우

DP를 이런식으로 위와 왼쪽에 한줄 더 넣어준 뒤 현재위치에서 board의 현재 위치와 왼쪽 위, 대각선 위의 값중 큰값으로 더해나가는 방식이다.

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

참고

https://pacific-ocean.tistory.com/204