[백준-11048번] 이동하기 풀이 - Java

🚀 문제

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

 

🚀 접근 방법

DP문제이다.

3가지 방향으로만 움직일 수 있다.

 

이동 위치에서 이전 위치+현재 위치 값을 더한 값과 다른 이동방향에서 더해진 값을 비교해서 더 큰 값을 저장하면 된다.

(총 3가지 방향에서 올 수 있으므로)

 

따라서 점화식은 아래와 같이 된다.

dp[nx][ny] = Math.max(dp[i][j]+map[nx][ny], dp[nx][ny]);

🚀 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


        int[] info = Arrays.stream(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = info[0];
        int m = info[1];

        int[][] map = new int[n][m];
        int[][] dp = new int[n][m];

        for(int i=0; i<n; i++){
            int[] point = Arrays.stream(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for(int j=0; j<point.length; j++){
                map[i][j] = point[j];
            }
        }

        int[] dx = new int[]{0, 1, 1};
        int[] dy = new int[]{1, 1, 0};

        dp[0][0] = map[0][0];

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                for(int k=0; k<3; k++){
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx>=n||ny>=m){
                        continue;
                    }
                    dp[nx][ny] = Math.max(dp[i][j]+map[nx][ny], dp[nx][ny]);
                }

            }
        }
        System.out.println(dp[n-1][m-1]);
    }
}