[프로그래머스 / 자바 / Lv.3] 43105 정수 삼각형

 

문제

 

풀이

 

 

DP 문제다. 트리에서 자식들의 누적합이 최대가되는 값을 출력하는 문제이다.

DP 점화식을 아래와 같이 생각했다.

{자식의 현재 값 + (오대각선위 or 왼대각선위) 중 최댓값} 을 구해서 단말노드에 누적 합을 넣어놓는다

 

이 점화식으로 DP에 누적합을 넣어놓으면 마지막 배열에 총 누적합의 경우가 쌓이므로 마지막 배열 중 최댓값을 출력하면 답이다.

 

class Solution {
    public int solution(int[][] triangle) {
        int len = triangle.length;
        int[][] dp = new int[len][len];

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

        for (int i=1; i<len; i++){
            dp[i][0] = triangle[i][0] + dp[i-1][0]; // 트리에서 왼쪽은 무조건 왼쪽끼리의 합이 가장 큼
            for (int j=1; j<i+1; j++){
                dp[i][j] += triangle[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]); // dp 점화식
            }
        }
        // dp[len-1] 배열(마지막 배열)이 각 누적합을 더한 부분이므로 여기서 최댓값이 정답
        int ans = Arrays.stream(dp[len-1]).max().getAsInt();
        return ans;
    }
}

 

1. dp 배열의 루트를 triangle 배열의 루트와 같게 설정해준다.

2. 트리에서 왼쪽 부분은 무조건 왼쪽끼리의 누적합이 최대이므로 그 부분을 먼저 계산해준다.

3. 위에서 세운 점화식을 코드로 짜면 다음과 같다.

DP[i][j] += triangle[i][j] + Math.max(dp[i-1][j-1], dp[j-1][j])

4. 마지막으로 stream을 이용해서 dp의 마지막 배열의 최댓값을 뽑아와서 반환하도록 구현했다.