[BOJ] 백준 11048 이동하기

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

 Input 

3 4

1 2 3 4

0 0 0 5

9 8 7 6

 

 Output 

31

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

각 칸에서 이동 방향은 (r+1, c), (r, c+1), (r+1, c+1)로 아래와 같습니다.

반대로 어느 지점 (i, j)에서 도달하는 방법은 아래와 같습니다.

dp[i][j] = dp[i][j]에 도달하는 경로에서 얻을 수 있는 최대값

               =  arr[i][j] + Max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

각 칸에는 음수가 없으며, 경로의 길이는 길어도 상관없으므로

경로②는 최대값을 얻기에는 적절치 않습니다.

▶ dp[i][j] = arr[i][j] + Max(dp[i-1][j], dp[i][j-1])

 

DP를 이용해 각 Test Case를 표현하면 아래와 같습니다.

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());
         
        int[][] arr = new int[N+1][M+1];
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                arr[i][j] = Integer.parseInt(sc.next());
            }
        }
        int[][] dp = new int[N+1][M+1];
         
        // 출발점 세팅
        dp[1][1] = arr[1][1];
         
        // dp 입장에서 위쪽, 왼쪽에서 오는 경로를 고려 (x, y) 조절
        // (대각선 방향은 제외)
        int[] rowMove = {0, -1};
        int[] colMove = {-1, 0};
         
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                if(!(i==1 && j==1)) {
                    // dp[i][j]라면 dp[i-1][j]와 dp[i][j-1]의 값을 저장할 것이다.
                    int[] temp = {0, 0};
                    // 배열범위 내인지 확인
                     
                    for(int k=0; k < rowMove.length; k++) {
                        int prev_x = i + rowMove[k];
                        int prev_y = j + colMove[k];
                        if(prev_x > 0 && prev_x <= N && prev_y > 0 && prev_y <= M) {
                            temp[k] = arr[i][j] + dp[prev_x][prev_y];
                        }
                    }
                     
                    // dp[i][j]에는 dp[i-1][j]와 dp[i][j-1] 중에서 큰 값을 취한다.
                    dp[i][j] = Math.max(temp[0], temp[1]);
                }
 
            }
        }
        System.out.println(dp[N][M]);
    }
}