로봇 조종하기
시간 제한1초메모리 제한512 MB
N x M 격자에서 좌우 이동과 아래 이동만 허용하고 셀을 재방문할 수 없을 때, 왼쪽 위에서 오른쪽 아래까지 최대 합 경로를 구하는 문제입니다.
문제
NASA는 화성 탐사를 위해 무선 조종 로봇을 보냈다. 실제 화성 지형은 매우 복잡하지만, 로봇의 메모리가 제한되어 있으므로 지형을 N x M 격자로 단순화한다.
고저차 때문에 로봇은 현재 칸에서 왼쪽, 오른쪽, 아래쪽으로만 이동할 수 있고 위쪽으로는 이동할 수 없다. 또한 이미 탐사한 칸은 다시 탐사하지 않는다.
각 칸에는 탐사 가치가 주어진다. 로봇은 왼쪽 위 칸 (1, 1)에서 출발해 오른쪽 아래 칸 (N, M)에 도착해야 한다. 이동 규칙을 지키면서 방문한 모든 칸의 가치 합이 최대가 되도록 하라.
입력
첫째 줄에 두 정수 N, M이 주어진다 (1 <= N, M <= 1,000).
다음 N개의 줄에는 각 줄마다 M개의 정수가 주어진다. 각 정수의 절댓값은 100 이하이며, 해당 칸의 탐사 가치를 나타낸다.
출력
방문한 칸들의 가치 합으로 얻을 수 있는 최댓값을 출력한다.