import java.util.*;
// 이동하기 - DP - S2
public class ex11048 {
static int n,m;
static int[][] board;
static int[][] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
board = new int[n+1][m+1];
dp = new int[n+1][m+1];
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
board[i][j] = sc.nextInt();
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
dp[i][j] = Math.max(dp[i][j-1]+board[i][j],dp[i-1][j]+board[i][j]);
}
}
System.out.println(dp[n][m]);
}
}
일단 문제를 읽어보면 DFS,BFS로 풀 수 있을 것 같은 느낌이 든다. 하지만 문제 조건을 보면 미로 조건이 최대 1000까지 주어진다. DFS,BFS로 풀면 백빵 런타임 에러가 뜬다. 그러면 뭐냐? -> 무조건 DP!! 바로 점화식을 찾아야한다.
주인공은 우측 , 우측 하단 대각선 , 아래 이렇게 3가지 방향으로 움직일 수 있다.
예를 들어,
1 4
3 4
이렇게 미로가 구성되어있다고 치자, 1이 (1,1)이라고 했을때 (2,2)로 가는 경우에 가장 많은 사탕 개수를 가지려면 무조건 대각선은 가지 않고 우측이나 아래를 거쳐 가야한다.
그렇기 때문에 점화식은
dp[i][j] = Math.max(dp[i][j-1]+board[i][j] , dp[i-1][j]+board[i][j])
이렇게 구성된다.