백준 1932 정수 삼각형(Java)

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

1932번: 정수 삼각형

---

 

해석 및 팁

 

---

 

이 문제는 위에서부터 다이내믹프로그래밍을 이용하면 되는 문제입니다. 점화식이 dp [i][j] = Max(dp[i-1][j] , dp[i-1][j-1] ) + arr [i][j] 이므로 먼저 arr배열에 값을 입력받은 후 dp배열의 값을 구하면 됩니다 그 후 dp [n]의 최댓값을 구하면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

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

    int max = -1;
    int n = sc.nextInt();
    int[][] arr = new int[n + 1][n + 1];
    int[][] dp = new int[n + 1][n + 1];
   
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= i; j++) arr[i][j] = sc.nextInt();
    }

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

    for(int i = 1; i <= n; i++) max = Math.max(max, dp[n][i]);

    System.out.println(max);
  }
}