문제 풀이(59)

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

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

class Main {

    static int n;
    static int[][] A;

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        A = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] str = br.readLine().split(" ");
            for (int j = 0; j <= i; j++) {                
                A[i][j] = Integer.parseInt(str[j]);
            }
        }

        // 동적 프로그래밍을 위한 DP 배열 사용하지 않고 A 배열 자체를 수정
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                // 왼쪽 끝일 경우
                if (j == 0) {
                    A[i][j] += A[i - 1][j];
                }
                // 오른쪽 끝일 경우
                else if (j == i) {
                    A[i][j] += A[i - 1][j - 1];
                }
                // 나머지 경우
                else {
                    A[i][j] += Math.max(A[i - 1][j - 1], A[i - 1][j]);
                }
            }
        }

        // 최대값을 찾기 위해 마지막 행을 순회
        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer = Math.max(answer, A[n - 1][i]);
        }

        System.out.println(answer);
    }
}