[프로그래머스] 정수 삼각형 - 자바 Java + 접근 방식

프로그래머스 -  https://school.programmers.co.kr/learn/courses/30/lessons/43105

 

Dynamic Programming 문제이고 아래 칸으로 아래로 내려가면서 거쳐간 숫자의 최댓값을 구하는 문제입니다.

 

접근 방식

크게 맨 왼쪽 값, 중간 값, 맨 오른쪽 구하는 식으로 구성되어있고 answer 를 업데이트하면서 현재까지 계산된 최대 합을 저장합니다. 

 

import java.util.*;

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