프로그래머스 Java 정수 삼각형

❓ 문제

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

프로그래머스

 

❗️ 풀이

이 문제는 DP(동적계획법)을 활용하는 문제다.

굳이 DP 배열을 따로 만들지 않고, 삼각형 아래에서부터 위로 올라가면서 최댓값을 갱신하는 방식(Bottom-Up DP 방식)으로 구현했다.

이렇게 하면 마지막에 triangle[0][0]에 최댓값이 남아서 그대로 return 하면 된다.

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