백준 11048. 이동하기

https://www.acmicpc.net/problem/11048

11048번: 이동하기

 

프로그래머스에서 푼 카카오 기출중에 거의 같은 문제가 있었는데 제목이 기억이 안난다.

현재 위치 (r,c)에서 오른쪽, 아래, 대각선 아래 로만 움직일수 있으므로 왔던 길을 되돌아 갈 수는 없다.

 

dp로 푸는데 각 칸을 왼쪽에서 오른쪽으로 현재 칸으로 왔을때와, 위에서 아래로 내려와 현재칸으로 왔을때를 나눈다.

이동은 대각선 아래로도 할 수 있지만 생각해보면 딱히 이동할수 없는 위치가 있는것도 아니고 최소횟수로 이동해야 하는것도 아니기 때문에 대각선 아래로 이동하는 것은 아래로 가는것과 오른쪽으로 가는 경우에 포함된다고 볼 수 있다.

 

점화식은 

d[0][i][j] = max(d[0][i][j-1] + a[i][j], d[1][i][j-1] + a[i][j]) 

d[1][i][j] = max(d[0][i-1][j] + a[i][j], d[1][i-1][j] + a[i][j]) 

 

(d[0]은 왼쪽에서 오른쪽으로 온 경우, d[1]은 위에서 아래로 온경우)