[Programmers] 정수 삼각형 (JAVA)

프로그래머스

 

풀이

 

DP문제는 항상 어려운 것 같다.

이 문제도 꽤나 오래 고민을 했는데 쉬운 풀이에 .. ^-^

내 실력에 약간 좌절을 했다. 

ㅎ

 

DP는 결국 아이디어가 중요하기 때문에 풀이를 보는 것 보다는 직접 생각하는 게 좋다고 해서

3시간정도 생각해서 풀어봤는데, BFS나 재귀 완탐으로 푸니까 시간초과가 발생해서 ㅎㅎ

 

삼각형 아래에서부터 제일 큰 것을 위에 더해주면 결국 맨 위로 도달할 수 있는건 최대합계이다.

이 생각을 왜 못했을까?!?

가지치기로 말하자면

A는 A1과 B1을 가지고 있는데, A1과 B1중에 큰 수를 A에 더해버리면

이후 상위 a에 A(A1+B1) B(A2+B2)중 큰 수를 더해주면 된다.

 

아직 모자란 실력이라는 걸 깨달았다 정진해야지.

 

전체코드

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