[알고리즘] 프로그래머스 - 정수 삼각형 (동적 계획법)

1. 문제

2. 문제 풀이

문제를 보자마자 이항 계수(파스칼의 삼각형)가 떠올랐고 대표적인 동적 계획법 문제이다. 동적 계획법은 최적화와 관있고 반복되는 계산을 줄일 수 있다. 심지어 문제에 최댓값이라는 힌트까지 있다. 일단 dp배열을 정의하였는데 예를 들어서 dp[3][2] 면 3행 2열까지 이동했을때 가장 큰수를 저장한다고 생각하였다. 그러면 dp[3][2] = max(dp[2][1], dp[2][2]) + triangle[3][2] 이런식으로 표현이 가능하다. 그러면 그러면 dp[2][1]도 base case로 부터 이러한 연산을 시작해서 올라올 것이다. 삼각형의 가장자리에 있는 경우와 나머지 경우를 나눠서 수식을 세웠다. 자세한 내용은 calculateDp 메소드를 보면 된다. 메소드 연산이 끝났으면 정답은 마지막 행에 해당하는 dp[height-1][i] 에서 가장 큰 수가 된다.

class Solution {
    private static int dp[][];

    public static void calculateDp(int[][] triangle, int height){

        dp[0][0] = triangle[0][0];

        for(int i=1;i<height;i++){  //행
            for(int j=0;j<i+1;j++){  //열
                if(j == 0){
                    dp[i][j] = dp[i-1][0] + triangle[i][j];
                } else if(j == i){
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                } else{
                    dp[i][j] = Math.max(dp[i-1][j-1] , dp[i-1][j]) + triangle[i][j];
                }
            }
        }

    }

    public static int solution(int[][] triangle) {

        //dp 배열 초기화
        int height = triangle.length;
        dp = new int[height][height];

        //dp 계산
        calculateDp(triangle, height);

        //정답
        int answer = 0;

        for(int i=0;i<height;i++){
            if(dp[height-1][i]>answer){
                answer = dp[height-1][i];
            }
        }

        return answer;
    }
}