문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

import sys

input = lambda: sys.stdin.readline().strip()

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

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

d = [[0] * m for _ in range(n)]
d[0][0] = arr[0][0]

for y in range(n):
  for x in range(m):
    for i in range(3):
      nx, ny = x + dx[i], y + dy[i]
      if nx < 0 or ny < 0 or nx >= m or ny >= n:
        continue
      d[ny][nx] = max(d[ny][nx], d[y][x] + arr[ny][nx])

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

백준 11048 이동하기