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

https://school.programmers.co.kr/learn/courses/30/lessons/43105#qna

프로그래머스

 

문제 풀이

바텀-업 방식으로 상위 값으로 올라갈 때 어떤 하위 노드를 거쳐야 최댓값이 되는지 비교하여 큰 값을 더하여 저장한다.

따라서 마지막에 triangle[0][0]을 리턴해주기만 하면 된다.

class Solution {
    public int solution(int[][] triangle) {
        for (int i=triangle.length-1;i>0;i--) {
            for (int j=0;j<triangle[i].length-1;j++) {
                triangle[i-1][j] += Math.max(triangle[i][j], triangle[i][j+1]);
            }
        }
        return triangle[0][0];
    }
}