백준 1932 정수 삼각

백준 1932 정수 삼각형

---

오늘은 dp 문제 정수 삼각형을 풀었다.
이전 최댓값들을 가지고 있다가 업데이트 해주기만 하면 되고,

맨 마지막 줄에서 가장 큰 값을 찾는걸 저번에 이용한 Collections.max를 이용해 보았다. 이를 위해 그냥 배열로 만든걸 list로 변경해주는게 필요 했는데, 다음번에 짤땐 시작부터 리스트로 할 수 있으면 좋을 것 같다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Boj_1932 {

    public static void main(String[] args) {
        int n;
        int table[][] = new int[502][502];
        int result[][] = new int[502][502];
        Scanner scanner = new Scanner(System.in);
        n = Integer.parseInt(scanner.nextLine());

        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(scanner.nextLine());
            int j = 1;
            while (st.hasMoreTokens()) {
                table[i][j] = Integer.parseInt(st.nextToken());
                j++;
            }
        }
        result[1][1] = table[1][1];
        result[2][1] = result[1][1] + table[2][1];
        result[2][2] = result[1][1] + table[2][2];
        for (int i = 3; i <= n; i++) {
            result[i][1] = result[i-1][1] + table[i][1];
            for (int j = 2; j < i; j++) {
                result[i][j] =Math.max(result[i-1][j-1], result[i-1][j]) + table[i][j];
            }
            result[i][i] = result[i-1][i-1] + table[i][i];
        }
        List<Integer> hoobo = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            hoobo.add(result[n][i]);
        }
        System.out.println(Collections.max(hoobo));
    }
}