N * M 배열에서 로봇은 왼쪽, 오른쪽, 아래쪽으로만 이동이 가능하다. 그리고 한 번 탐사한 지역은 다시 탐사하지 않도록 한다. 그리고 각 배열의 칸에는 숫자(-100 ~ 100)가 적혀있는데, 이 때, (0, 0)에서 (N - 1, M - 1)까지 이동하면서 지나간 칸의 숫자의 합이 최대가 되도록 이동하고, 그 최대값을 구하는 문제이다.
dp를 이용해서 구할 것인데, 예를들어, (r, c)에서 출발해서 (N - 1, M - 1)칸 까지의 칸의 숫자의 합을 구할 때, (r, c - 1), (r, c + 1), (r + 1, c) 칸 중 어느 칸으로 이동해야 숫자의 합이 최대가 되는 경로인지 볼 것인데, 단순히 (row, column) 정보로는 부족하다.
같은 (r, c - 1)라고 해도 직전 경로가 위인지, 왼쪽인지, 오른쪽인지(어디에서 왔는지)에 따라 다음에 갈 수 있는 경로가 다르게 결정된다. 예를들어, 왼쪽에서 왔다고 하면 한 번 탐사한 지역은 다시 탐사하면 안되기 때문에 오른쪽이나 아래쪽으로 가야한다. 그래서 어떤 방향에서 왔는지에 대한 정보가 필요하다.
그리고 dp를 이용해서 풀 때, 평소 dp배열을 -1로 초기화하고 -1이 아니면 답을 구했다고 판단하고 리턴해줬는데, 이 문제의 경우 데이터에 음수값이 있기 때문에, 따로 boolean check배열을 만들어서 이미 그 부분에 대해 답을 구했는지 아닌지 판단한다.
그리고, 또 실수할 수 있는 부분이 있다면, 최대값을 구할 때, max값을 0으로 초기화해놓고, 비교해서 최대값을 구하는 것에 익숙한데, 위에서 말했듯이 음수값이 있기 때문에 0으로 초기화하면 안되고, 모든 입력이 -100으로 들어온다고 가정하고 그에 해당하는 1000 * 1000 * (-100) 으로 max값을 초기화 해줄 필요가 있다.
아니면, 그냥 max값에 바로 구한 값을 대입하면서 시작하는 방법도 있다. 이 방법은 굳이 나올 수 있는 최소값이 얼마일까 고민할 필요도 없고, 그렇기에 실수할 가능성도 적다.
