[백준 11048] 이동하기 -JAVA //le_effort//

알고리즘 : DP

반대로 생각해서 했다.

이동 가능한 방향이 r+1,c      r,c+1     r+1 c+1 으로 가능 한 데

 

도착 칸 기준으로

동그라미 칸에서 올 수 있는 것은 저기 화살표 친 방향들

즉 r-1 c-1   /   r-1 c  / r c-1

이렇게 올 수 있다

 

이렇게 하면 반복문을 진행 할 때 인덱스 오류를 범하지 않을 수 있다

저기 빨간색 친 부분은 기존의 맵보다 1 크게 받았는데

반복문이 1,1 부터 시작해도 인덱스 오류가 나지 않고 빨간칸은 어차피 0 으로 되어있으므로 값에 오류가 없다 라는 것을 설명하기 위해 그린 것

 

dp[r-1][c-1] dp[r-1][c]  dp[r][c-1] 중 가장 큰 값과 현재 칸의 값 map[r][c]를 더해주면 답이 나온다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int n,m;
    static int map[][];
    static int dp[][];
    static int dx[] = {1,0,1};
    static int dy[] = {0,1,1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        dp = new int[n+1][m+1];
        map = new int[n+1][m+1];
        for(int i=1; i<=n; i++) {
            String[] input = br.readLine().split(" ");
            for(int j=1; j<=m; j++) {
                map[i][j] = Integer.parseInt(input[j-1]);
            }
        }
        dp[1][1] = map[1][1];
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                dp[i][j] = Math.max(dp[i-1][j-1],Math.max(dp[i-1][j], dp[i][j-1]))+map[i][j];
            }
        }
        System.out.println(dp[n][m]);
    }
}