백준 1932번: 정수 삼각형

문제 출처: https://www.acmicpc.net/problem/1932

DP(Dynamic Programming)로 푼다.

arr[i][j] 값은 arr[i-1][j-1]값과 arr[i-1][j]값 중 큰 값과 arr[i][j]값을 더한 값이다.

arr[i-1][j-1]가 범위에서 벗어나면 0으로 초기화하여 비교한다.

arr[0][0] = 7

arr[1][0] = max(arr[0][-1], arr[0][0]) + arr[1][0] = max(0, 7) + 3 = 10

arr[1][1] = max(arr[0][0], arr[0][1]) + arr[1][1] = max(7, 0) + 8 = 15

arr[2][0] = max(arr[1][-1], arr[1][0]) + arr[2][0] = max(0, 10) + 8 = 18

arr[2][1] = max(arr[1][0], arr[1][1]) + arr[2][1] = max(10, 15) + 1 = 16

arr[2][2] = max(arr[1][1], arr[1][2]) + arr[2][2] = max(15, 0) + 0 = 15

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[][] arr = new int[n][n];
 
        StringTokenizer tokenizer;
        for(int i=0 ; i<n ; i++){
            tokenizer = new StringTokenizer(reader.readLine());
            for(int j=0 ; j<i+1 ; j++){
                arr[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }
 
        for(int i=1 ; i<n ; i++){
            for(int j=0 ; j<i+1 ; j++){
        // left(arr[i-1][j-1]) 값과 right(arr[i-1][j]) 값 중 큰 값을 arr[i][j] 값에 더한다.
                arr[i][j] += Math.max((j==0) ? 0 : arr[i-1][j-1], arr[i-1][j]);
            }
        }
 
        Arrays.sort(arr[n-1]);
        System.out.println(arr[n-1][n-1]);
    }
}