P43105. 정수 삼각형

문제

제출 코드

• 사용 알고리즘 : dp
• 주어진 삼각형 배열과 똑같은 배열을 만들어서, 위에서부터 순차적으로 내려오면서 현재 칸까지의 합의 최대값을 저장한다.
• 삼각형의 테두리에 속하는 양 끝의 칸은, 대각선 위의 칸이 유일하므로 해당 칸에서 현재칸의 값을 더해 저장한다.
• 그 이외의 안쪽에 속하는 칸은, 대각선 위가 두가지 경우가 있으므로 오른쪽 위와 왼쪽 위 중 더 큰 값에 현재 값을 더해 저장한다

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        // 1. dp 값 저장할 배열 생성
        int depth = triangle.length;
        int[][] dp = new int[depth][depth];

        // 2. 맨 윗줄에서부터 순차적으로 누적 최대값 저장
        dp[0][0] = triangle[0][0];
        for(int i=1; i<depth; i++){
            dp[i][0] = dp[i-1][0] + triangle[i][0]; // 왼쪽 가장자리
            dp[i][i] = dp[i-1][i-1] + triangle[i][i]; // 오른쪽 가장자리
            for(int j=1; j<i; j++) dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]; // 안쪽
        }

        // 3. 마지막 줄에서의 최댓값 구하기
        int answer = -1;
        for(int num : dp[depth-1]) answer = Math.max(answer, num);
        return answer;
    }
}