백준|1932번|정수 삼각형

문제설명
정수 삼각형에서 아래에 있는 수들중 하나를 선택해서 내려올 때 선택된 수들의 합에서 최댓값을 출력하는 문제입니다.

작동 순서
1. 삼각형의 크기 n을 입력받습니다.
2. 삼각형의 숫자들을 입력받습니다.
3. 각 위치로 가는 경로의 최대합들을 구합니다.(그 줄의 첫번째 원소거나 마지막 원소인 경우 선택할 수 있는 경우의 수가 하나밖에 없고 아닌 경우 자신에게 올 수 있는 두 경로 중 더 큰 숫자를 선택합니다.)
4. 경로의 최대값을 찾고 그 값을 출력합니다.

소스코드

import java.io.*;
import java.util.*;
public class 백준_1932번_정수삼각형{
    public static void main(String[] args) throws IOException{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int max = 0;
        int[][] triangle = new int[n+1][];
        int[][] dp = new int[n+1][];
        for(int i=1;i<n+1;i++){
            triangle[i]=new int[i];
            dp[i]=new int[i];
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<i;j++) triangle[i][j]=Integer.parseInt(st.nextToken());
        }
        dp[1][0]=triangle[1][0];
        for(int i=2;i<n+1;i++){
            for(int j=0;j<i;j++){
                if(j==i-1) dp[i][j]=triangle[i][j]+dp[i-1][j-1];
                else if(j>0) dp[i][j]=triangle[i][j]+Math.max(dp[i-1][j], dp[i-1][j-1]);
                else dp[i][j]=dp[i-1][j]+triangle[i][j];
            }
        }
        for(int i=0;i<n;i++){
            if(max<dp[n][i]) max=dp[n][i];
        }
        System.out.print(max);
    }
}