[프로그래머스] 정수 삼각형 - JAVA

https://programmers.co.kr/learn/courses/30/lessons/43105?language=java#_=_

문제 해석

정수 삼각형 최상단에서
왼쪽 또는 오른쪽으로 내려가면서 값을 더해갈때
가장 최댓값은?

제한사항
삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

문제 풀이

모든 경우의 수를 해본다면? O(2^n)
내려가면서 왼쪽 또는 오른쪽 숫자를 사용했을때 최댓값만 남긴다 O(n^2)

최대값을 구할때 sorting을 사용해도 된다
Arrays.sort(arr);

//내림차순
Integer []arr = {1, 2, 0};
Arrays.sort(arr, Collections.reverseOrder());

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int i, j, right, left;

        for(i = 1; i < triangle.length; i++){
            for(j = 0; j < triangle[i].length; j++){
                left = right = 0;

                if(j - 1 >= 0){
                    left = j - 1;
                    left = triangle[i][j] + triangle[i - 1][left];
                }

                if(j < triangle[i - 1].length){
                    right = j;
                    right = triangle[i][j] + triangle[i - 1][right];
                }

                triangle[i][j] = left > right ? left : right;
            }
        }

       for(int x: triangle[i - 1]){
           if(x > answer) answer = x;
       }

        return answer;
    }
}