프로그래머스 - 정수삼각형 문제 (자바)

programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

삼각형의 모양을 아래와 같이 생각하고 풀면 쉽게 풀린다.

|\
| \
|  \
----

 

1. 맨 왼쪽의 경로는 바로 위에서 오는 경로 뿐이므로 우선 계산한다.

2. 이후 맨 왼쪽과 맨위를 제외한 영역을 순회하면서 누적값을 구한다.

  - 바로 위와 왼쪽 대각의 값 중 높은 값과 본인을 합쳐서 계산

3. dp의 맨 마지막 줄 중에 가장 큰값을 리턴

// 프로그래머스 정수삼각형 문제
class Triangle {
    public int solution(int[][] triangle) {
        int[][] dp = new int[triangle.length][triangle[triangle.length-1].length + 1];
        dp[0][0] = triangle[0][0];

        // 삼각형 맨 왼쪽은 바로 위의 값과의 합이 dp값
        for(int i = 1; i < triangle.length; i++) {
            dp[i][0] = dp[i-1][0] + triangle[i][0];
        }

        for(int i = 1; i < triangle.length; i++) {
            for(int j = 1; j < triangle[i].length; j++) {
                // 구하고자하는 위치의 바로 위와 대각선 위의 값 중 큰값과의 합
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }

        // dp 맨 마지막 줄에서 가장 큰값
        int answer = 0;
        for(int value : dp[triangle.length-1]) {
            answer = Math.max(answer, value);
        }
        return answer;
    }
}