[Silver II] 이동하기 - 11048 : Java (DP)

1. 문제

11048번: 이동하기

문제 설명

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

 

---

 

2. 어떻게 풀까?

현재 위치에서 얻을 수 있는 사탕의 최댓값을 구할 수 있어야 한다. 현재 위치에 올 수 있는 방법은 문제에 주어진 대로 3가지가 있다. (r-1, c), (r, c-1), (r-1, c-1) 이다. 이 3좌표에서 얻을 수 있는 가장 많은 사탕의 수에서 현재 위치의 사탕을 더해주면 된다.

 

즉 현재 위치에서 얻을  수 있는 최대 사탕의 개수는  `Max((r-1, c), (r, c-1), (r-1, c-1)에서 얻은 사탕 수))` + `현재 위치의 사탕의 개수`이다. 

 

3. 약간의 팁

3가지 방향을 체크해야 되기 때문에, 다소 귀찮은 작업이 배열의 범위를 벗어나지 않는지 체크하는 것이다. 이 과정을 줄이기 위해 나는 `윗 방향`에 대해 범위 체크를 안할 수 있도록, 첫 줄(r=0)을 먼저 초기화 시키고 진행했었다. (배열의 크기를 N+1, M+1로 설정하면 사실 별다른 범위 체클르 하지 않아도 된다..!)

 

하지만 단순히 배열의 크기를 늘리는 것으로 부족할 떈, 인덱스에러나 널 에러가 나지 않을 어떤 한 방향에 대해 고정 시킨 다음, 범위 체크 후 더 높은 값에 대해 갱신해주면 코드가 간단해질 수 있다.

dp[r][c] = dp[r-1][c];
// 대각선 방향
if(r-1 >=0 && c-1 >=0) {
    dp[r][c] = Math.max(dp[r][c], dp[r-1][c-1]);
}
// 왼쪽 옆 방향
if(c-1 >=0) {
    dp[r][c] = Math.max(dp[r][c], dp[r][c-1]);
}

 

 

4. 전체 코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception  {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int [][] A = new int[N][M];
        int [][] dp = new int[N][M];


        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j <M; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[0][0] = A[0][0];
        // 디폴트 값으로 설정하기 위해 미리 데이터 채워주기 -> 윗 방향에 대해 범위체크 안해도 됨
        for(int i=1; i<M; i++) {
            dp[0][i] = dp[0][i-1] + A[0][i];
        }

        // 세 방향을 체크하고 max값으로 갱신 (위, 왼쪽 옆, 대각선)
        for(int r=1; r<N; r++) {
            for(int c =0; c<M; c++) {

                dp[r][c] = dp[r-1][c];
                // 대각선 방향
                if(r-1 >=0 && c-1 >=0) {
                    dp[r][c] = Math.max(dp[r][c], dp[r-1][c-1]);
                }
                // 왼쪽 옆 방향
                if(c-1 >=0) {
                    dp[r][c] = Math.max(dp[r][c], dp[r][c-1]);
                }
                // 현재 위치에 있는 사탕 더하기
                dp[r][c] += A[r][c];
            }
        }
        System.out.println(dp[N-1][M-1]);
    }


}