[BOJ][DP] 11048. 이동하기

문제 링크 -> https://www.acmicpc.net/problem/11048

꽤 간단한 DP 문제라고 생각한다.

현 위치를 (x , y)라 할 때, 가능한 이동 방법은

(x+1, y), (x, y+1), (x+1, y+1) 이렇게 세가지이다.

그런데, 가만 생각해보면 굳이 대각선으로 갈 필요가 없지 않나?

대각선으로 바로 통과하는 것 보다 한 곳을 더 거쳐서 가는게 더 사탕을 많이 먹을 수 있을텐데?

위 사진에서 볼 수 있듯이 바로 대각선 이동 보다는 우->하 or 하->우 로 가는것이 더 최대의 이익을 누릴 수 있다.

따라서 나는 대각선으로 가는 경우는 그냥 배제해버렸다. 

고로 점화식은 아래와 같이 나온다.

dp[i][j] = Max(dp[i-1][j], dp[i][j-1]) + maze[i][j])

Max 는 대소비교를 하는 함수. 

아, 그리고 원래 미로에 있던 값을 바꿔서는 안된다. 그렇게 되면 결과가 아예 바뀌기에 따로 배열을 하나더 만들어 저장해야한다.

소스(Github)