32.정수 삼각형

📍 문제 설명

💡 접근

2번째 행부터 오른쪽 위에서 내려오거나 왼쪽 위에서 내려오는 거리를 기록한다.

마지막 행 중 최댓값 출력

 

👩‍💻 코드

import java.util.*;

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

        int n = kb.nextInt();
        int[][] arr = new int[500][500];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                arr[i][j] = kb.nextInt();
            }
        }

        //경로의 합을 저장해놓는 dp 테이블 초기화
        int[][] dp = new int[500][500];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                dp[i][j] = arr[i][j];
            }
        }

        //두번째 줄 부터 거리를 기록해 나간다.
        //i = 1 j = 0, 1
        //i = 2 j = 0, 1, 2
        for(int i = 1; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                int leftDown, rightDown;
                //오른쪽 위에서 내려올 때(바로 위)
                leftDown = dp[i][j] + dp[i-1][j];
                //왼쪽 위에서 내려올 때(왼쪽  위)
                if(j == 0) rightDown = 0;
                else rightDown = dp[i][j] + dp[i-1][j-1];
                dp[i][j] = Math.max(leftDown, rightDown);
            }
        }

        int result = 0;
        for(int i = 0; i < n; i++) {
            result = Math.max(result, dp[n-1][i]);
        }
        System.out.println(result);
    }
}