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

코딩테스트연습(동적계획법) - 정수 삼각형

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

프로그래머스

문제 설명

삼각형의 꼭대기에서 시작하여 오른쪽아래 또는 왼쪽아래로 차례로 내려가면서 바닥까지 내려간다.

그 경로에서 거쳐간 숫자의 합이 가장 큰 경우 그 합을 구하는 문제이다.

삼각형의 높이는 1~500이다.

삼각형을 이루고 있는 숫자는 0~9999이다.

---

문제 풀이

생각 과정

우선 정답배열과 임시배열을 만드는데 그 길이는 삼각형의 최하단의 길이만큼 설정한다.

그리고 삼각형의 최상단에서부터 차례로 내려오면서 정답배열에 넣어주면서 갱신한다.

최상단은 기본으로 넣어주고 

그 다음부터는 좌상단과 우상단 중 큰 값을 넣는다.

이런 과정을 끝까지 반복하면 

각 경로에 따른 숫자의 합은 아래와 같다.

이 중 가장 큰 25가 정답이 된다.

구현

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