kingsubin

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

public class boj_1932 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static long[][] dp;
    static int[][] val; // 0 ~ 9999
    static int n; // 1 ~ 500

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        dp = new long[n+1][n+1];
        val = new int[n+1][n+1];

        // 맨 위가 1층 , 맨 아래가 n층
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; j++) {
                val[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = val[i][j];
            }
        }

        // n-1층부터 1층까지 구해가야함
        for (int i = n-1; i >= 1; i--) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] += Math.max(dp[i+1][j], dp[i+1][j+1]);
            }
        }

        // 1층까지올라온 최댓값
        System.out.println(dp[1][1]);
    }
}

 

- 제일 아래층부터 올라가는 식으로 찾았음

- 초기 dp 에는 val값을 그대로 넣고, 제일 아래의 윗층 n-1층 부터 dp 시작 

- i-1 층의 왼쪽 j와 오른쪽 j+1 중 큰것을 dp에 + 하는식으로 더하는 식으로 올라감

- 결국 최상단부인 [1][1] 에는 최댓값이 들어옴