[프로그래머스 lv 3] 정수 삼각형.java

<문제 설명>

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

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

문제 설명에 이미지가 필요한 관계로 위 링크에 직접 접속해서 보는 것이 편할 것이다.

 

입출력의 예는 다음과 같다.

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

 

<문제 풀이 아이디어>

 

거쳐온 숫자의 최대값을 리턴해야 하므로 항상 최적의 해를 보장하는 알고리즘인 DP(동적 계획법)을 사용하기로 했다.

triangle[0][0]의 위치에서부터 하나씩 내려오면서 가질 수 있는 경우의 수중 가장 최대값을 가진 방법을 매번 비교해서 그 방법으로 진행하고자 했다.

 

<문제 풀이 코드>

class Solution {
    public int solution(int[][] triangle) {
        
        int[][] dp = new int[triangle.length][triangle.length];
        dp[0][0] = triangle[0][0];
        
        for(int i = 1;i<triangle.length;i++){
            dp[i][0] = triangle[i][0] + dp[i-1][0];
            for (int j=1; j<i+1; j++) {
                dp[i][j] = triangle[i][j] + Math.max(dp[i -1][j - 1], dp[i -1][j]);
            }
        }
        int max = 0;
        for (int i=0; i<dp[dp.length - 1].length; i++) {
            max = Math.max(dp[dp.length - 1][i], max);
        }

        
        int answer = max;
        return answer;
    }
}

 

채점 결과