[Lv.3] 정수 삼각형

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        //up left = i-1, up right= 1,
        //dp[n][k][0] , dp[n][k][1]중에 최대를 dp[n+1][k][1], n,k-1에서 최대를 dpn k 0로 ..
        int[][][] dp=new int[triangle.length+1][triangle.length+1][2];
        dp[0][0][0]=dp[0][0][1]=triangle[0][0];
        for (int i = 1; i < triangle.length; i++) {
            dp[i][0][0]=0;
            dp[i][0][1]=Math.max(dp[i-1][0][0],dp[i-1][0][1])+triangle[i][0];
            int end=triangle[i].length-1;
            dp[i][end][0]=Math.max(dp[i-1][end-1][0],dp[i-1][end-1][1])+triangle[i][end];
            dp[i][end][1]=0;
            for (int j = 1; j < end; j++) {
                dp[i][j][0]=Math.max(dp[i-1][j-1][0],dp[i-1][j-1][1])+triangle[i][j];
                dp[i][j][1]=Math.max(dp[i-1][j][0],dp[i-1][j][1])+triangle[i][j];
            }
        }
        for (int i = 0; i < triangle[triangle.length - 1].length; i++) {
            answer=Math.max(answer,dp[triangle.length-1][i][0]);
            answer=Math.max(answer,dp[triangle.length-1][i][1]);
        }




        return answer;

    }
}

---

간단한 DP문제였다.