[Lv. 3] 정수 삼각형

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++) {
            //Left
            dp[i][0] = dp[i - 1][0] + triangle[i][0];            
            //root
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
            }
            // Right
            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를 사용해서 풀었다. 가장 맨 왼쪽과 오른쪽 숫자들은 구조상 고를 필요가 없이 쭉 내려오면 되는데 가운데 값들은 합계에 따라 어떤 값을 선택할지 골라줘야 한다.  

 

1. p 배열을 초기화하고 첫 번째 삼각형 요소를 dp[0][0]에 할당
2. 이중 반복문을 사용하여 각 행마다 최대 합을 계산
   • 첫 번째 반복문(i 반복문)은 행을 나타내며, 각 행마다 왼쪽, 가운데, 오른쪽 세 부분을 처리
   • 두 번째 반복문(j 반복문)은 현재 행의 열, 현재 위치의 최대 합은 이전 행의 왼쪽과 오른쪽 위치 중 최대값을 현재 위치의 값과의 합
3. 마지막 행의 각 열에서 얻은 최대 합 중 가장 큰 값을 answer에 할당