이동하기 - 11048

문제

풀이

import java.util.*;

// 이동하기 - DP - S2
public class ex11048 {
    static int n,m;
    static int[][] board;
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        board = 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++){
                board[i][j] = sc.nextInt();
            }
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                dp[i][j] = Math.max(dp[i][j-1]+board[i][j],dp[i-1][j]+board[i][j]);
            }
        }
        System.out.println(dp[n][m]);

    }

}

일단 문제를 읽어보면 DFS,BFS로 풀 수 있을 것 같은 느낌이 든다. 하지만 문제 조건을 보면 미로 조건이 최대 1000까지 주어진다. DFS,BFS로 풀면 백빵 런타임 에러가 뜬다. 그러면 뭐냐? -> 무조건 DP!! 바로 점화식을 찾아야한다.

주인공은 우측 , 우측 하단 대각선 , 아래 이렇게 3가지 방향으로 움직일 수 있다.

예를 들어,

1 4
3 4

이렇게 미로가 구성되어있다고 치자, 1이 (1,1)이라고 했을때 (2,2)로 가는 경우에 가장 많은 사탕 개수를 가지려면 무조건 대각선은 가지 않고 우측이나 아래를 거쳐 가야한다.

그렇기 때문에 점화식은

dp[i][j] = Math.max(dp[i][j-1]+board[i][j] , dp[i-1][j]+board[i][j])

이렇게 구성된다.