[백준] 로봇 조종하기_2169

cache[y][x] = 현재 위치에서 앞으로 더 얻을 수 있는 최대 가치  

이렇게 두고 풀었는데, 저 테스트케이스를 통과하지 못해서 계속 틀렸다. cache를 방향까지 고려해서 3차원 배열로 해야한다는 것을 미처 생각하지 못했다. 7이 나와버림.. 

 

4 4 
1 1 1 1 
-1 -1 -1 1 
1 1 1 1 
100 -10 1 1

 

1 1 1 1 
-1 -1 -1 1 
1 1 1 1 
100 -10 1 1

 

최대 가치(101)를 얻으려면 이렇게 움직여야 한다. 

현재 위치에서 앞으로 더 얻을 수 있는 가치는 그 전 방향에 따라 다르다. 따라서 위치 + 방향까지 고려해서 3차원 배열을 사용해야 한다. 

왼쪽에서부터 왔다면 다시 왼쪽으로는 못 갈테니깐, 다른 방향으로 가서 최댓값을 저장하게 된다. 

하지만 다른 방향에서 왔다면 왼쪽으로도 갈 수 있을 것이고, 새로운 최대 가치가 나올 수도 있다. 2차원 배열로만 선언하면 위의 왼쪽에서부터 왔던 경우의  cache 값을 받고 끝나버릴 것이고, 그럼 정답과는 다른 결과가 나올 수 있다. 

예를 들어 mars[3][4]의 위치에서 (이 문제는 좌표가 1, 1에서부터 시작) 왼쪽 방향에서 온 경우, 아래로 간다면 추가로 얻을 가치가 1일 것이다. 하지만 위쪽 방향에서 와서 왼쪽으로도 이동한다면 100을 얻어서 최대 가치가 훨씬 많아진다. 

그런데 2차원 배열로만 선언한다면 저 1도 최대 가치라고 생각하고 더 이상 탐색하지 않을 것이고, 오답이 나오게 된다. 

 

욕심쟁이 팬더같은 문제랑은 좀 다르다. 팬더는 일단 왼쪽에서 왔든 위쪽에서 왔든, 이 위치에서 다음 값이 더 많아야만 이동할 수 있었다. 어떤 경우에서건 결국 현재 위치의 값으로만 앞으로의 최대 가치가 달라진다.