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

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

프로그래머스

 

 

Idea

아래에서 위로 올라가면서 계산하는 방식으로 풀어야겠다고 생각했다. 0번째 줄에서 1번째 줄의 두 경로 중 큰 수 선택, 1번째 줄에서 2번째 줄의 두 경로 중 큰 수 선택 ... length - 2 번째 줄에서 length - 1번째 줄의 두 경로 중 큰 수 선택 순으로 이어진다. 즉, 맨 아래 줄은 계산할 필요가 없으니까 triangle.length - 2 부터 계산했다. 현재 위치에서 두 경로 중 더 큰 경로를 선택하다보면, triangle[0][0] 에 최종 경로 합이 저장된다.

 

 

Code

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