[프로그래머스][정수 삼각형]-Lv.3

🎈문제

문제링크

🎈접근방법

Dynamic Programmin(DP)를 이용하였다.

7 0 0 0 0
3 8 0 0 0
8 1 0 0 0
2 7 4 4 0
4 5 2 6 5

이런식으로 보는 것이 더 편할 것이다. 각 줄에 첫번째 숫자들은 바로 위칸 첫번째 숫자로만 영향이 미치기 때문에 그 값을 먼저 구하고 두번째 숫자들부터는 위에 숫자와 왼쪽 대각선에 있는 숫자중 큰것을 더한다.

🎈코드

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=1; i<triangle.length; i++){
            dp[i][0] = triangle[i][0] + dp[i-1][0];
            
            for(int j=1; j< i+1; j++){
                dp[i][j] = triangle[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);
                if(i==triangle.length-1){
                    answer = Math.max(answer, dp[i][j]);
                }
            }
        }
        return answer;
    }
}