[백준] 1932 정수 삼각형 자바(Java)

문제설명

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

 

출력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

 

통과한 코드 ✅

import java.util.*;
import java.io.*;

public class Main {
    static int[][] arr;
    static Integer[][] dp;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        arr=new int[n][n];
        dp= new Integer[n][n];

        for(int i=0; i<n; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0; j<i+1; j++){
                arr[i][j]=Integer.parseInt(st.nextToken());
            }
        }

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

    public static int find(int depth, int idx){
        //맨 밑에 도달하면 해당 인덱스 반환
        if(depth==n-1) return dp[depth][idx];

        // 만약 아직 탐색하지 않았다면 다음 행의 양쪽 열 중 최대값 구함
        if(dp[depth][idx]==null){
            // 왼쪽, 오른쪽 대각선인 바로 다음행의 인덱스와 그 오른쪽의 인덱스 중
            // 큰 값 찾아 dp에 현재 인덱스와 더하여 저장
            dp[depth][idx]= Math.max(find(depth+1,idx),find(depth+1,idx+1))+arr[depth][idx];
        }
        return dp[depth][idx];
    }
}