[DP] 정수 삼각형 - JAVA

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

프로그래머스

 

---

DP니까 그냥 위에서 아래로 내려오면서 그때마다 큰 값을 저장하는 방식으로 했다

여기서 분기를 3가지로 했는데 

첫번쨰는 위의 경우!

이때는 내려올 수 있는 곳이 바로 위밖에 없으니까 그냥 더해줬다

 

두 번쨰는 이 경우!

이것도 위에 밖에 안되니까 그냥 더해줬다

 

마지막은 이 경우!

이 떄는 2가지 중 더 큰 값을 더해주는 방식으로 했다

 

생각보다 쉽게 푼 문제였다!

 

 

자바 코드)

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int n = triangle.length;

        for(int i=1;i<n;i++) {
            for(int j=0;j<=i;j++) {
                int temp = triangle[i][j];
                if(j==0) {
                    temp += triangle[i-1][j];
                }
                else if(i==j) {
                    temp += triangle[i-1][j-1];
                } else {
                    temp += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
                }
                triangle[i][j] = temp;
            }
        }
        for(int i=1;i<n;i++) {
            if(answer<triangle[n-1][i]) {
                answer = triangle[n-1][i];
            }
        }
        return answer;
    }
}