[백준] 1932번 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

다음 줄과 현재 줄의 최대값을  비교하여 갱신한 후에

다음줄에 그에 해당하는 배열값을 더함

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

public class Main {

    public static void main(String[] args) throws Exception {

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

        dp[1][1] = arr[1][1];
        for(int i=1; i < n; i++) {
            for(int j=1; j <=i; j++) {
            	// 왼쪽 j, 오른쪽 j+1
            	// 최대값으로 갱신
            	dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);
            	dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j]);
            }
            // 최대값에 배열값 플러스 해줌
            for(int j=1; j<=n; j++) {
            	dp[i+1][j] += arr[i+1][j];      
            }

        }

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