프로그래머스 - 정수 삼각형

Java

정수 삼각형

문제

접근 방법

삼각형의 높이를 n이라고 하면, 맨 아래 줄의 원소 개수도 n개이다.

각 위치까지 내려오면서 만들 수 있는 최대 합을 저장하기 위해 n x n 크기의 2차원 배열을 생성하고 이를 DP 배열로 사용한다.

dp[i][j] 는 i,j 지점까지 내려 왔을 때, 가장 비용이 큰 것을 담는 객체

점화식 도출

삼각형의 구조상, triangle[i][j] 위치로 내려올 수 있는 경우는 두 가지뿐이다.

• 바로 위에서 내려오는 경우 → dp[i-1][j]
• 위에서 왼쪽 한 칸에서 내려오는 경우 → dp[i-1][j-1]

따라서, dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

코드

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int n = triangle.length;
        int[][] dp = new int[n][n];
        dp[0][0] = triangle[0][0];

        for(int i = 1; i < n; i++ ) {
            for(int j = 0; j < triangle[i].length; j++) {
                for(int k = -1; k <= 0; k++) {
                    if(j + k < 0)
                        continue;
            
                    if(dp[i][j] < dp[i-1][j + k]  + triangle[i][j]) {
                        dp[i][j] = dp[i-1][j + k]  + triangle[i][j];
                    }
                }
            }
        }

        for(int i = 0; i < n; i++) {
            answer = Math.max(answer, dp[n-1][i]);
        }
        return answer;
    }
}