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

문제

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

풀이

(x,y)로 가기 위해서는 (x-1, y), (x-1, y-1) 에서 갈 수 있다
즉, triangle(x-1, y)+triangle(x, y) 와 triangle(x-1, y-1)+triangle(x,y) 중에서 최대값이 (x, y) 값

DP[x][y] = Math.max( DP[x-1][y] + tri[x][y] , DP[x-1][y-1] + tri[x][y] )
그리고 맨 왼쪽줄은 바로 위의 요소만 더할 수 있고, 맨 오른쪽 줄은 바로 왼쪽 위의 요소만 더할 수 있으므로 예외로 빼놓고 생각한다.

코드

/**
* 지금까지의 합 + 현재 위치의 값 을 구하면서 최대값을 구한다.

**/

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int len = triangle.length;
        
        answer = triangle[0][0];
        
        if(len > 1){
            for(int i=1; i<len; i++){
                for(int j=0; j<=i; j++){
                    
                    if(i==j){ // 맨 오른쪽 줄인 경우
                        triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]; // 왼쪽 위까지의 합 + 현재 값
                    } else if (j == 0){ // 맨 왼쪽 줄인 경우
                        triangle[i][j] = triangle[i-1][j] + triangle[i][j];
                    } else {
                        triangle[i][j] = Math.max(triangle[i-1][j] + triangle[i][j], triangle[i-1][j-1] + triangle[i][j]);
                    }
                    
                 answer = Math.max(triangle[i][j], answer);  
                }
            }
            
        }

        return answer;
    }
}