[백준 11048] 이동하기

 

 

dp 배열에 사탕의 최대값을 저장하면서 풀면된다.

 

1	2	3	4
0	0	0	5
9	8	7	6

 

오른쪽, 아래, 대각선으로 이동하므로 가장자리의 줄은 더해서 채워준다.

 

1	3	6	10
1	0	0	5
10	8	7	6

 

나머지 칸들은 [i-1][j-1], [i-1][j], [i][j-1] 중 최대값을 저장한다.

 

1	3	6	10
1	3	6	15
10	18	25	31

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[][] = new int[n][m];
        int dp[][] = new int[n][m];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        dp[0][0] = a[0][0];
        for(int i=1; i<n; i++) {
            dp[i][0] = dp[i-1][0] + a[i][0];
        }
        for(int i=1; i<m; i++) {
            dp[0][i] = dp[0][i-1] + a[0][i];
        }
        
        for(int i=1; i<n; i++) {
            for(int j=1; j<m; j++) {
                dp[i][j] = max(max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + a[i][j];
            }
        }
        
        System.out.println(dp[n-1][m-1]);
    }
    
    public static int max(int a, int b) {
        return a > b ? a : b;
    }
}