프로그래머스 정수 삼각형

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

코드

class Solution {
    
    public int solution(int[][] triangle) {
        int answer = Integer.MIN_VALUE;

        int[] arr = {};
        int[] tmp = {};

        arr = new int[1];
        arr[0] = triangle[0][0];

		// [0]번째 행은 연산할 것이 없으므로, [1]번째 행부터 반복문 실행
        for(int i=1; i<triangle.length; i++) {
        	// 연산을 위한 배열 i*2개
            tmp = new int[i*2];

            int idx = 0;
            for(int j=0; j<arr.length; j++) {
               tmp[idx++] = arr[j] + triangle[i][j];
               tmp[idx++] = arr[j]+ triangle[i][j+1];
            }

			// 해당 열의 원본 데이터는 i+1개 이므로, 
            // 중간 원소들은 대소비교를 통해 더 큰 값을 추린 후 i+1개 값만 저장한다.
            arr = new int[i+1];
            arr[0] = tmp[0];
            arr[i] = tmp[i*2-1];

            idx = 1;
            for(int j=1; j<tmp.length-2; j+=2) {
                arr[idx++] = Math.max(tmp[j], tmp[j+1]);
            }
        }

		// 마지막 연산 결과 값중 MAX 값 찾기
        for(int i=0; i<arr.length; i++) {
            if(answer < arr[i]) answer = arr[i];
        }
        
        return answer;
    }
}

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

프로그래머스