[java 백준] 실버 1/ 11048번 이동하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static int n,m;
    public static int [][]dp;
    public static int [][]arr;
   
 
 
    public static void main(String[]args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        arr=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++){
                arr[i][j]=sc.nextInt();
 
 
            }
 
        }
 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
 
                dp[i][j]=arr[i][j]+Math.max(dp[i-1][j],Math.max(dp[i][j-1],dp[i-1][j-1]));
 
            }
        }
 
        System.out.println(dp[n][m]);
 
 
 
 
    }
 
 
}
 

 

 

처음에는 BFS로 풀었는데 그냥 dp로 풀어주는게 맞았다. 생각해보니 누적합의 최대값이니까 ㅇㅇ

다른 사람은 Math.max안에서 arr값을 비교했는데 나는 dp로 비교했다. arr[i][j]는 당연히 더해주고, 아래에서 위를 바라보는건데 이말은 즉슨 지금까지 더해진 누적값 중 더 큰걸 더해주는게 더 쉽다고 판단했기 때문이다!!