[JAVA/코딩테스트] 정수 삼각형

문제

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

프로그래머스

 

풀이

class Solution {
    public int solution(int[][] triangle) {

        int answer = 0;

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

        answer = triangle[0][0];

        return answer;
    }
}

 

처음에 DFS로 풀었다가 시간초과가 떠서 봤더니 거꾸로 계산하는 방법이 있더라

거꾸로 계산하면서 자식 노드에 있는 값들을 더해 가장 큰 값을 저장하고 저장하고 해서 계산하였다.

 

다이나믹프로그래밍은 한번만 계산해야한다는게 핵심인 것 같다.