[프로그래머스] 정수 삼각형(자바) / DP

문제

 

입력&출력

 

문제풀이

import java.util.*;
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 = 0 ; i<triangle.length-1;i++ ){
            for(int j=0;j<=i;j++){
                dp[i+1][j]=Math.max(dp[i][j]+triangle[i+1][j],dp[i+1][j]);
                dp[i+1][j+1]=Math.max(dp[i][j]+triangle[i+1][j+1],dp[i+1][j+1]);
            }
        }
        for(int i = 0 ; i < triangle.length;i++){
            answer = Math.max(dp[triangle.length-1][i],answer);
        }
        return answer;
    }
}

 

※ 내 생각

이 문제는 DP를 활용하는 문제입니다.

DP의 정석 같은 느낌으로 문제풀이를 진행하면 됩니다.
주어진 배열 크기 만큼의 DP 배열을 만들어 줍니다.
각 칸에 대해 for 문을 돌리면서 DP 배열에 최댓값을 넣어줍니다.
마지막 줄의 dp를 for문을 돌려 최댓값을 찾아줍니다.