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

- 문제

프로그래머스

- 풀이

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        //삼각형의 높이를 쉽게 사용하기 위해 len을 만들어 놓습니다.
        int len = triangle.length;
        
        //삼각형을 내려오며 더해지는 과정을 dp로 표현하기 위해
        //triangle과 크기가 같은 ArrayList<>를 만들어줍니다.
        ArrayList<int[]> arr = new ArrayList<>();
        for(int i=1; i<=len; i++){
            arr.add(new int[i]);
        }
        
        //꼭대기의 값은 더 더해질 값이 없으므로 동일하게 채워줍니다.
        arr.get(0)[0] = triangle[0][0];
        
        //이제 꼭대기의 다음 칸부터 탐색을 시작합니다.
        //핵심은 단순합니다. "현재 층의 현재 칸에 올 수 있는 위층의 값들 중 더 큰 값을 현재 칸에 더해준다."를
        //반복합니다.
        for(int i=1; i<len; i++){ //각 층을 표현해줍니다. 0층(꼭대기층)은 고정이므로 1층부터 시작합니다.
            for(int j=0; j<=i; j++){ //각 층의 칸들을 표현해줍니다.
                
                //각 층의 0번째 인덱스와 i번째 인덱스는 상단에서 내려올 수 있는 값이 하나 뿐입니다.
                //따라서 하나 뿐인 값을 그대로 더해줍니다.
                if(j==0){
                    arr.get(i)[j] = arr.get(i-1)[j] + triangle[i][j];
                } else if(j==i){
                    arr.get(i)[j] = arr.get(i-1)[j-1] + triangle[i][j];
                    
                //가운데 칸들의 값은 좌(i-1), 우(i)양쪽의 값을 받아올 수 있습니다.
                //따라서 Math.max를 이용해 두 값중 큰 값을 현재의 위치 값에 더해줍니다.
                } else {
                    arr.get(i)[j] = Math.max(arr.get(i-1)[j-1], arr.get(i-1)[j]) + triangle[i][j];
                }
                
                //구할 수 있는 모든 값 중 만들어 질 수 있는 최대 값을 구하는
                //것이 목적이므로 만들어지는 모든 값을 탐색하며 최대값을 찾아줍니다.
                answer = Math.max(arr.get(i)[j], answer);
            }
        }
        
        //구해진 답을 반환합니다.
        return answer;
    }
}