이동식 저장소

코로나19의 빠른 종식을 기원합니다. 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 지형을 탐사하며, 탐사 가치를 최대로 해야 하는 문제이다. 이때 로봇은 오른쪽, 왼쪽, 아래로만 움직일 수 있으며, 한 번 방문한 지역은 다시 방문할 수 없다. 전형적인 완전 탐색 문제이다. 그러나 완전 탐색으로는 최대 O(3^(N+M))을 감당할 수 없으므로 동적 계획법(이하 dp)을 활용해야 한다. 관찰 로봇은 위쪽으로 움직일 수 없다. 따라서 지형의 마지막 행에 도착한 로봇은 반드시 오른쪽으로만 이동해야 한다...