문제

인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있으며, 그 외의 방향으로 움직이는 것은 불가능하다. WOOK은 자신이 위치한 (x, y)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다. WOOK이 탐사할 영역에 대한 정보가 주어질 때, WOOK이 탐색할 수 있는 자원의 최대 숫자를 구해라!

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, dy = [1, 0], [0, 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(2):
      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])

max_ore = 0
for ore in d:
  max_ore = max(ore+[max_ore])

print(max_ore)

백준 14430 자원 캐기