[프로그래머스] 정수 삼각형- 자바

처음에는 dsp로 푸는 문제인 줄 알고 이것저것 시도하다가...

뭔가 이상해서 찾아보니 DP를 통해서 푸는 문제인 걸 알게 되었다.....

이 때의 허무감은 말을 할 수가 없다...ㅠㅠㅠ

 

처음에는 왜 안풀리지 했는데 이렇게 푸니까 해결....

이것도 허무함...일단 문제를 풀었으니 업로드 한다

 

 

public class Triangle {
    public int solution(int[][] triangle) {;
        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 + 1][j + 1]);
            }
        }
        return triangle[0][0];
    }

    public static void main(String[] args) {
        Triangle triangle = new Triangle();
        int[][] ex = new int[][]{{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
        System.out.println(triangle.solution(ex));
    }
}

 

 

 

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