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

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

코딩테스트 연습 - 정수 삼각형

2021-08-30

---

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

#문제풀이

꼭대기에서부터 계산할 때, 다음 트리의 본인 인덱스와 본인 인덱스+1에 영향을 끼치게 된다. 

 

그리고, 그 다음 트리에는 두 가지 이상의 값이 들어올 수 있으므로, max값을 체크해줘야한다.