[프로그래머스] 프로그래머스 Level3 정수 삼각형 Java

문제

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

풀이

DP를 통해 해결할 수 있었다. DP[i][j]가 i,j의 좌표가 가질 수 있는 거쳐간 숫자의 최댓값이라고 가정했을 때 이 문제는 점화식은 3개로 나뉘는데

i) 삼각형의 왼쪽 끝일 때 - dp[i][j] = dp[i - 1][j] + triangle[i][j]

ii) 삼각형의 오른쪽 끝일 때 - dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];

ii) 삼각형의 왼쪽 끝, 오른쪽 끝이 모두 아닐 때 - dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];

그 이유는 예를들어 삼각형의 왼쪽 끝일 때(j =0)는 위로 왼쪽 대각선 좌표에 대한 값이 존재하지 않고, 삼각형의 오른쪽 끝일 때(j = i)는 위로 오른쪽 대각선 좌표에 대한 값이 존재하지 않기 때문이다. 그 외에는 위로 왼쪽 대각선 좌표, 위로 오른쪽 대각선 좌표의 값이 모두 존재하므로 이렇게 분기에 따른 3개의 점화식을 도출해낼 수 있다.

점화식을 통해 DP 테이블을 모두 채웠다면 그게 끝이 아니고 거쳐간 숫자의 최댓값을 삼각형의 가장 아랫쪽의 DP 테이블 중 최댓값을 구해주어 정답을 도출해낼 수 있다.

코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;

        int[][] dp = new int[502][502];

        dp[0][0] = triangle[0][0];
        dp[1][0] = triangle[1][0] + dp[0][0];
        dp[1][1] = triangle[1][1] + dp[0][0];

        for(int i = 2; i < triangle.length; i++) {
            for(int j = 0; j <= i; j++) {
                if(j == 0) {
                    dp[i][j] = dp[i - 1][j] + triangle[i][j];
                } else if(j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
                }
            }
        }

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

        return answer;
    }
}