[프로그래머스] level3 43105 - 정수 삼각형(Java)

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=java

접근 방법

더해가면서 최댓값을 구한다.

3가지의 경우가 존재한다.

1. 왼쪽으로만 쭉 더해주는 것과
2. 오른쪽으로만 쭉 더해주는 것과
3. 그 사이에서 바로 윗줄에서의 둘 중 더 큰 값을 더해주는 것
   

이를 기록해가며 진행하면 된다.

소스 코드

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