정수 삼각형

Seongjin Jo·2023년 5월 17일
0

프로그래머스 LV3

목록 보기
2/4

문제

풀이

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int[][] dp = new int[501][501];
        
        dp[0][0] = triangle[0][0]; // 처음엔 하나라서 그냥
        dp[1][0] = dp[0][0] + triangle[1][0]; //10
        dp[1][1] = dp[0][0] + triangle[1][1]; //15
        
        //양 끝 먼저 구해주고
        for(int i=2; i<triangle.length; i++){
            dp[i][0] = dp[i-1][0] + triangle[i][0];
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];
        }
        
        //가운데 Math.max로 최대값 설정
        for(int i=2; i<triangle.length; i++){
            for(int j=1; j<i; j++){
                dp[i][j] = Math.max(dp[i-1][j-1]+triangle[i][j] , dp[i-1][j]+triangle[i][j]);
            }
        }
        
        for(int x : dp[triangle.length-1]) answer = Math.max(answer,x);

        return answer;
    }
}

프로그래머스 DP문제이다. 제한사항이 500이하라서 최대합을 저장할 dp배열을 501로 선언해준다.
테이블을 0,1 번까지 정의 해준다.

그리고 이 문제를 푸는 방법
우선, 각 양쪽의 끝에 합을 다 구해놓는다. 그리고 겹치는 부분들을 Math.max로 더 큰 값을 집어 넣는다.
생각을 잘 해야한다. DP는 ,,,,

0개의 댓글