[백준] 정수 삼각형 - JAVA

문제

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

1932번: 정수 삼각형

 

코드

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

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+1;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dp[1][1] = arr[1][1];
		
		for(int i=2;i<=n;i++) {
			for(int j=1;j<i+1;j++) {
				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1])+arr[i][j];
			}
		}
		
		int max = 0;
		for(int i=1;i<=n;i++) {
			max = Math.max(max, dp[n][i]);
		}
		
		System.out.print(max);

	}
	
}