dynamic programming 6

문제는 더블릿 21 dynamin programming에 있는 scv입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/scv/scv.php?pname=scv

N*N의 맵의 왼쪽 위에서 시작하여 오른쪽, 아래로 움직이면서 최대한 많이 1을 거쳐갈 수 있도록 하는것이 문제입니다.

전형적인 dp문제 중 하나로 힌트는 오른쪽 혹은 아래로만 움직일 수 있다는데에 있습니다.  오른쪽이나 아래로만 움직일 수 있으므로 map[i][j]번 째 scv는 map[i-1][j] 혹은 map[i][j-1]에서 온 것이 됩니다.  이 때 map[i][j]번 째의 scv가 많은 미네랄을 갖고 있으려면 map[i][j]에 미네랄이 있든 없든 우선 map[i-1][j] 혹은 map[i][j-1] 중에 많은 미네랄을 갖고 있던 곳에서 map[i][j]로 오는 것이 유리합니다.

즉, 다음 위치에서 많은 미네랄을 가지려면 그곳에 올 수 있는 그 전 위치 중 많은 미네랄을 가진 곳에서 와야한다는 것입니다.  결국 scv는 map[N][N]의 위치까지 올 것이며 그전에 많은 미네랄을 먹을 수 있는 길을 거쳐야합니다.  map[N][N]에서 많이 먹기 위해선 map[N-1][N] 혹은 map[N][N-1]에서 와야하며 이곳들에서 많이 먹기 위해선 그 전 위치에서도 많이 먹어야 합니다.  이를 처음부터 끝까지 돌려주면 map[N][N]의 위치에선 최대한 많이 먹었을 때의 미네랄을 가지게 됩니다.