[Java] 11048번 이동하기

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

(r+1,c) ↓, (r,c+1) →, (r+1,c+1) ↘ 로 이동할 때 가져올 수 있는 사탕 개수의 최댓값
r+1,c+1 = ↘ 대각선은 최댓값이 나올 수 없으므로,(대각선 = ↓→ , →↓ 이렇게 갈 수 있기 때문에 )
0,0 부터 이동하며 아래로 갈 때와 오른쪽으로 갈 때 중 Max값을 구한다.
미로의 최대크기가 1000 이므로, dfs 는 탈락.. DP!

3. 코드

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

public class Main {

    static int N,M;
    static int[][] arr;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        // 값 불러오기 -->
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        arr = new int[N][M];
        dp = new int[N+1][M+1];

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

        // 0,0 에서 출발하므로, 초기값 설정
        dp[1][1] = arr[0][0];

        // 최대 갯수 구하기
        for(int i=1;i<N+1;i++){
            for (int j=1;j<M+1;j++){
                dp[i][j] = Math.max( dp[i-1][j] , dp[i][j-1]) + arr[i-1][j-1];
            }
        }

        System.out.println(dp[N][M]);
    }

}

백준예시 1을 통한 , dp의 값
예시값)
3 4
1 2 3 4
0 0 0 5
9 8 7 6

dp)
0, 0, 0, 0, 0
0, 1, 3, 6, 10
0, 1, 3, 6, 15
0, 10, 18, 25, 31

으로, 최댓값이 잘 구해지는 걸 볼 수 있당