[Java] Lv.3 정수 삼각형

문제

 

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

프로그래머스

 

문제 풀이

위에서 아래로 내려가며 계산하면 고려할게 너무 많다.

BOTTOM - UP 방식으로 위로 올라가면서 계산한다.

한 줄로 표현하면 n층 i번과 i + 1번 중 더 큰 값을 n - 1층 i번에 더한다.

그러면 맨 위층에는 아래서부터 더해서 올라온 값 중 가장 큰 값이 저장되고 그 값을 반환한다.

자바 코드

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int[][] dp = new int[triangle.length + 1][triangle.length];
        
        // 맨 아래층부터 검사해나간다.
        for(int i = triangle.length - 1; i > 0; i--){
            for (int j = 0; j < triangle[i].length - 1; j++) {
                // 현재 위치에서 한 층 위의 숫자에 
                // 현재 위치와 현재 위치 + 1 값 중 더 큰 값을 더 함
                triangle[i - 1][j] += Math.max(triangle[i][j], triangle[i][j + 1]);
            }
        }
        
        // 최종적으로 삼각형의 맨 위에 최대 합이 저장됨
        return triangle[0][0];
    }
}