백준 11048 이동하기(Java)

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

11048번: 이동하기

---

 

해석 및 팁

 

---

 

이 문제는 다이나믹프로그래밍을 활용하는 문제입니다. dp[i][j]는 지금까지 가져올 수 있는 사탕의 개수의 최댓값이이라고 하면 점화식은 dp[i][j] = Math.max(dp[i - 1][j - 1], Math.max(dp[i - 1][j], dp[i][j - 1])) + arr[i][j] 입니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

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

    int n = sc.nextInt();
    int m = sc.nextInt();
    int[][] arr = new int[n + 1][m + 1];
    int[][] dp = new int[n + 1][m + 1];
    
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= m; j++) arr[i][j] = dp[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 - 1][j - 1], Math.max(dp[i - 1][j], dp[i][j - 1])) + arr[i][j];
    }

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