[백준] 1932 - 정수 삼각형 [JAVA]

 

코드

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

public class Main{
    static Integer[][] dp;
    static int[][] arr;
    static int N;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        dp = new Integer[N][N];
        arr = new int[N][N];

        StringTokenizer st;

        // 입력값 초기화
        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());
            }
        }

        // 제일 밑에 depth 초기화
        for (int i = 0; i < N; i++) {
            dp[N - 1][i] = arr[N - 1][i];
        }

        System.out.println(solution(0, 0));

    }

    static int solution(int depth, int idx) {

        // 제일 밑 뎁스면
        if (depth == N - 1) {
            return dp[depth][idx];
        }

        if (dp[depth][idx] == null) {
            // 왼쪽 오른쪽중 큰 값
            dp[depth][idx] = Math.max(solution(depth + 1, idx), solution(depth + 1, idx + 1)) + arr[depth][idx];
        }

        return dp[depth][idx];
    }
}