[프로그래머스] 동적 계획법 - 정수 삼각형

이 문제는 지난 컴퓨터 알고리즘 수업시간에 설명을 들은 적이 있다..

그거와는 별개로 기억나지 않는 풀이법..

 

그래서 동적계획법을 이용하여 어떻게 해결할까를 고민하니

거꾸로 올라가자라는 생각이 떠올랐고

맨 아래줄을 제외한 아랫줄에서 부터 새로운 정수 삼각형을 만들어

그 삼각형에서 만들 수 있는 가장 큰 수를 저장하게 하였다.

 

    static 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+1][j+1]);
        	}
        }
        
        return triangle[0][0];
    }

 

이 문제에서 위에서 아래로 내려가는 풀이법은 완전 탐색일 것이다.

이 경우 효율성 테스트에서 정답을 못 맞힌다..