프로그래머스 동적계획법(Dynamic Programming) 정수 삼각형 자바

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

프로그래머스

 

거쳐간 숫자의 최댓값을 구해야 하는데,

위에서부터 밑으로 내려오면서 비교하면 복잡해진다. 

어차피 최댓값 하나만 구하면 되기 때문에 

밑에서부터 올라가면서 최댓값을 더해 마지막 꼭대기에 최댓값이 남도록 하자. 

 

그럴려면 기존의 삼각형이 아닌,

더한 값을 저장하는 빈 삼각형이 필요하다.

빈 삼각형의 마지막 줄은 기존 삼각형과 동일하다. (베이스 동일)

 

class Solution{

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

}