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

문제

 

 

분석

DP 문재다. DP 문제는 메모이제이션이라고도 하는데

계산된 값을 저장해 두었다가 다시 사용하는 것을 말한다.

 

위에서 부터 누적합을 만들어 내려 가면된다.
주의점은 누적된 값 + 선택할수 있는 값 중에 최대 값이다.

 

 

 

 

구현

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

        for(int i =0 ; i <triangle[triangle.length-1].length; i++) {
            if (answer < triangle[triangle.length-1][i] ) {
                answer = triangle[triangle.length-1][i];
            }
        }
        return answer;
    }
}

 

 

결과