11048 (1) 썸네일형 리스트형 [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].. 이전 1 다음
