백준 11048 이동하기

n, m = map(int, input().split())

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

check = [[-1] * m for _ in range(n)]
check[0][0] = g[0][0]

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

for i in range(1, m):
    check[0][i] = check[0][i-1] + g[0][i]
for i in range(1, n):
    check[i][0] = check[i-1][0] + g[i][0]    
for i in range(1, min(m, n)):
    for j in range(i, n):
        for k in range(3):
            nx, ny = j + dx[k], i + dy[k]
            check[j][i] = max(check[j][i], check[nx][ny])
        check[j][i] += g[j][i]
    for j in range(i+1, m):
        for k in range(3):
            nx, ny = i + dx[k], j + dy[k]
            check[i][j] = max(check[i][j], check[nx][ny])  
        check[i][j] += g[i][j]

print(check[n-1][m-1])

그냥 dp 문제
처음에 for 문 범위 잘 못 설정해서 헤맴
탐색으로 풀 수 없을까 고민해보기....되면 한다