[Programmers] 동적 계획법 > 정수 삼각형 (Java)

문제 링크

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

프로그래머스

 

 

문제 요약

삼각형의 위에서 밑으로 한 칸씩 내려가면서 숫자를 더한다.

triangle의 길이만큼 반복한다.

합한 값이 가장 큰 걸 구한다.

 

 

 

구현 착안

한 칸씩 내려가면서 숫자를 더하므로 내려갈 때 선택에 따라 값이 변경된다.

이 말은 즉, 이전까지의 값이 모두 같기 때문에 중복 연산을 피하려면 동적 계획법으로 풀 수 있다.

 

 

구현 방식

밑으로 내려가는 방법에는 세 가지가 있다.

내려가면서 선택의 여지가 없으면 맨 모서리(1, 3번)로만 가고, 선택할 수 있으면 중간에서 최댓값을 찾아서 간다(2번).

 

1. 맨 왼쪽 변을 따라 내려간다.

2. 최댓값을 찾아서 간다.

3. 맨 오른쪽 변을 따라 내려간다.

 

 

직관적 이해를 위해 2번에 break point를 걸어서 디버깅해봤다.

 

 

 

제출 코드

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

        for(int i = 1; i < triangle.length; i++) {
            dp[i][0] = dp[i - 1][0] + triangle[i][0];

            for(int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
        }

        for(int i = 0; i < triangle.length; i++) {
            answer = Math.max(answer, dp[triangle.length - 1][i]);
        }

        return answer;
    }
}

dp[triangle.length - 1][i]는 삼각형 맨 밑의 바닥에 있는 숫자들이다.

dp에 저장된 값은 그간 걸어온 길들이 모두 최댓값일 때를 선택하여 더한 값이다.

마지막 for문에서 바닥에 있는 숫자 중 가장 큰 값을 찾으면 거쳐간 숫자의 합이 가장 큰 경우가 된다.

 

 

 

 

 

 

참고 : https://easybrother0103.tistory.com/133