정수 삼각형

문제 : 정수 삼각형

 

- 출력: 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는다.
- 조건: 아래 칸으로 이동할 때에는 대각선 방향으로 한 칸 오른쪽 or 왼쪽으로만 이동 가능

- 해결 방법:
[ DFS or DP ] 이 중 DP를 활용해 중복해서 거쳐가는 곳의 값을 따로 저장해 사용합니다.

예를 들어서 설명해보면 위 그림에서 
 1) [ 8,1,0 ] 에서 1은 7+3 / 7+8 중 큰 값을 골라주면 됩니다.
 2) [ 2,7,4,4 ] 에서 
 		- 7은 (7+3+8) / (7+8+1) 중에 큰 값을 고르게 됩니다.
 		- 4는 (7+8+0) / (7+8+1) 중에 큰 값을 고르게 됩니다.
        
이렇게 계산은 맨 왼쪽값, 중간값, 맨 오른쪽 값을 나눠서 계산하게 됩니다.
그러면 저장될 배열인 dp[][] 에는 dp[i-1][j-1], dp[i-1][j] 중 큰 값 + 현재 선택된 값이 들어가게 됩니다. 


- 점화식 : dp[i][j] = MAX(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

 

 

[ 작성 코드 ]

public static 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];
            // 7+3, 7+8, 7+2 와 같이 맨 왼쪽 부분을 더하게 된다.
            // dp[1][0] (10) = dp[0][0] (7) + triangle[1][0] (3) -- 1
            // dp[2][0] (18) = dp[1][0] (10) + triangle[2][0] (8) -- 2

            /* 중간값 */
            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[1][1] = dp[0][1], dp[0][0] 중에 max + triangle[1][1] (8) -- 1
                // dp[2][1] = dp[1][1], dp[1][0] 중에 max + triangle[2][1] (1)
                // dp[2][2] = dp[1][2], dp[1][1] 중에 max + triangle[2][2] (0) -- 2
            }

            /* 맨 오른쪽 */
//            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
            // dp[1][1] (15) = dp[0][0] (7) + triangle[1][1] (8) -- 1
            // dp[2][2] (15) = dp[1][1] (중간값의 max 값) + triangle[2][2] (1) -- 2

            for (int w = 0; w < dp.length; w++) {
                for (int k = 0; k < dp.length; k++) {
                    System.out.print(dp[w][k] + " ");
                }
                System.out.println();
            }

            System.out.println("------------------------------");
        }

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

        return answer;
}

* 위 DP 문제에는 중간 값 구할 때 맨 오른쪽 값도 같이 구해지기 때문에 맨 오른쪽 구하는 경우를 주석 처리 하였습니다.