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

프로그래머스

 

# 핵심

DP

삼각형 밑바닥에서부터 올라가기!

 

 

# 통과 코드

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

        // dp 배열 초기화
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < triangle[i].length; j++) {
                dp[i][j] = triangle[i][j];
            }
        }

        // 삼각형 밑바닥부터 꼭대기 직전까지~
        for(int i = len - 1; i > 0; i--) {
            for(int j = 0; j < triangle[i].length; j++) {
                if(j - 1 >= 0) { // 범위 초과에 유의
                    dp[i - 1][j - 1] = Math.max(dp[i - 1][j - 1], triangle[i - 1][j - 1] + dp[i][j]);
                }
                if(j < triangle[i - 1].length) { // 범위 초과에 유의
                    dp[i - 1][j] = Math.max(dp[i - 1][j], triangle[i - 1][j] + dp[i][j]);
                }
            }
        }

        return dp[0][0]; // 꼭대기에 최댓값이 남는다
    }
}

 

DP 문제라고 하면 덜컥 겁부터 나는데 이번 문제는 다행히도 크게 어렵지 않게 풀 수 있었당

 

그냥 삼각형 밑바닥에서부터 올라가면서 최댓값 경우의 수를 dp 배열에 저장해나가면 된다.

 

배열 인덱싱에 있어서 범위 초과 안나게끔 신경 써주는 것이 이번 문제에 있어서 중요한 점이었던 것 같다.

 

너무 좋습니다~~

다른 문제도 이만큼 잘 풀리면 얼마나 좋을꼬