DP :: 백준 :: 숫자삼각형 :: 1932

숫자삼각형 1932

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

[문제풀이]

작성중

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int row = Integer.parseInt(br.readLine());
 
        int[][] triangle = new int[row + 1][row + 1];
        String[] tmp;
        for (int i = 1; i <= row; i++) {
            tmp = br.readLine().split(" ");
            for (int j = 1; j <= i; j++) {
                triangle[i][j] = Integer.parseInt(tmp[j - 1]);
            }
        }
 
        int[][] max = new int[row + 1][row + 1];
        max[1][1] = triangle[1][1];
        int prevMax;
        for (int i = 2; i <= row; i++) {
            for (int j = 1; j <= row; j++) {
                if (j == row) {
                    max[i][j] = max[i - 1][j - 1] + triangle[i][j];
                    continue;
                }
                prevMax = max[i - 1][j - 1] > max[i - 1][j] ? max[i - 1][j - 1] : max[i - 1][j];
                max[i][j] = prevMax + triangle[i][j];
            }
        }
        int ans = 0;
        for (int i = 1; i <= row; i++) {
            ans = ans > max[row][i] ? ans : max[row][i];
        }
        System.out.println(ans);
    }
}