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

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

문제

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

 

문제 분석

조건

• 아래처럼 정수로 이루어진 삼각형이 주어진다.
• 맨 위에서 시작해서 아래로 내려가며 인접한 수를 선택해 내려올 때, 최댓값이 되는 경로의 합을 구하는 문제

    [7]
   [3, 8]
  [8, 1, 0]
 [2, 7, 4, 4]
[4, 5, 2, 6, 5]

풀이방법

• 아래에서부터 위로 올라가며 각 칸에서 선택 가능한 두 자식 중 큰 값을 더해 `triangle`값을 업데이트 해주는 방식으로 구하였다.

코드

class Solution {
    public int solution(int[][] triangle) {
        int floor = triangle.length - 1;
        for (int r = floor - 1; 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] ;
    }
}