[프로그래머스] 정수 삼각형 (java)

🔗 문제링크

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

👩🏻‍💻 코드

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

        dp[0][0] = triangle[0][0];
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                if (j == 0) {   // 가장 왼쪽
                    dp[i][j] = dp[i - 1][0] + triangle[i][j];
                } else if (j == triangle[i].length - 1) {  // 가장 오른쪽
                    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];
                }
            }
        }

        int len = triangle.length;
        for (int i = 0; i < len; i++) {     // 마지막 줄에서 가장 큰 수
            answer = Math.max(answer, dp[len - 1][i]);
        }

        return answer;
    }
}

📝 정리

DP 문제답게 위에서부터 더한 값을 배열에 저장해 주면 되었다.
가장 왼쪽과 가장 오른쪽은 위 계산이 그대로 내려오지만, 중간에 속하는 것들은 자신의 왼쪽 위와 오른쪽 위 중에서 더 큰 값을 선택해 더해주어야 했다.
그러고 나서 마지막 줄에서 가장 큰 수를 선택하면 된다.

✔️ DP 문제라는 걸 알고 풀어서 그런가 Level 3인 것에 비해 쉽게 느껴졌다.
✔️ 규칙을 찾는 것 또한 다른 DP 문제에 비해 쉬운 편인 것 같다.