[백준 알고리즘] 1932번 정수 삼각형 (JAVA)

---

주의 사항

• 첫번째와 마지막번째 그리고, 그 외의 순서에서의 점화식이 다르다. 
• i = 첫번째, i = 마지막, i = 두번째 ~ 마지막 -1 까지의 점화식을 세워 풀자.
  • i = 첫번째 -> dp[i][j] = dp[i-1][j] + matrix[i][j]
  • i = 두번째 ~ 마지막 - 1 -> dp[i][j] = dp[i-1][j-1] + matrix[i][j]
  • i = 마지막 -> Math.max(dp[i-1][j-1], dp[i-1][j]) + matrix[i][j]
    • 왼쪽 대각 위, 오른쪽 대각 위 중 큰 값을 넣어줘야 한다.

 

---

코드 블럭

package boj401;

import java.util.Scanner;

public class boj_1932 {

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

        int n = scanner.nextInt();

        scanner.nextLine();

        long[][] matrix = new long[n+1][n+1];

        for (int i = 1; i <= n; i++) {
            String[] s = scanner.nextLine().split(" ");

            for (int j = 1; j <= s.length; j++) {
                matrix[i][j] = Integer.valueOf(s[j - 1]);
            }

            for (int j = s.length + 1; j <= n; j++) {
                matrix[i][j] = 0;
            }
        }

        long[][] dp = new long[n + 1][n + 1];

        if (n == 1) {
            System.out.println(matrix[1][1]);
            return;
        } else if (n == 2) {
            System.out.println(Math.max(matrix[1][1] + matrix[2][1], matrix[1][1] + matrix[2][2]));
            return;
        }

        dp[1][1] = matrix[1][1];
        dp[2][1] = matrix[1][1] + matrix[2][1];
        dp[2][2] = matrix[1][1] + matrix[2][2];


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

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

        System.out.println(max);

    }

}