[Java] 백준 11048 : 이동하기

문제 링크

1.

익숙한 DP 문제.

비슷한 유형의 문제를 풀어봐서 그런지 점화식이 딱 보였다.

 

 

2.

dp[i][j]는 지금까지 가져올 수 있는 사탕의 개수의 최댓값이다.

이는 위, 왼쪽, 왼쪽 위 중 큰 값을 기준으로 현재 위치의 사탕 값을 더 해주면 된다.

 

다만, 나는 왼쪽 위를 기준으로 잡지 않았다.

이는 최단 경로를 구하는 문제라면 고려해줘야 하겠지만 사탕 개수의 최대를 구하는 문제인데 사탕 개수가 감소할 일이 없기 때문에 그렇다.

 

 

3.

import java.util.Scanner;

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

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

        int[][] data = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                data[i][j] = sc.nextInt();
            }
        }

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + data[i][j];
            }
        }

        System.out.println(dp[n][m]);
        sc.close();
    }
}

 

 

4.

none