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

문제 유형에 DP라고 쓰여있었기 때문에 어떻게 DP로 구현해야 할지 고민을 많이 했다.

점화식을 떠올리기 쉽기 때문에 레벨 3보다는 레벨 2에 더 적합한 문제라는 생각이 들었다.

Bottom-up 방식이 가장 먼저 떠올라서 풀었지만 Top-down 방식으로도 풀이가 가능할 것 같다.

---

로직

가장 밑에 층에서부터 가장 위층까지 올라가며 각 층의 최댓값을 찾는다.

그 층에서 최댓값을 찾았다면 바로 위층에 i - 1에 해당하는 값을 더해서 바꿔준다.

결과적으로 가장 위층에는 최댓값이 남게 된다.

 

점화식은 triangle[i - 1][j] = triangle[i - 1][j] + triangle[i][j] 의 최댓값이다.

---

최종 코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int sum = 0;
		
        // bottom-up 방식
        for (int i = triangle.length - 1; i >= 0; i--) {
            for (int j = 0; j < triangle[i].length - 1; j++) {
                sum = triangle[i][j] > triangle[i][j + 1] ? triangle[i][j] : triangle[i][j + 1];
                triangle[i - 1][j] += sum;
            }
        }

        answer = triangle[0][0];
        return answer;
    }
}