[프로그래머스] 정수 삼각형 - Java(자바)

 

문제 이해

• 삼각형의 꼭대기에서 바닥까지 이어오는 경로중 숫자의 합이 가장 큰 경우를 찾아라
• 이 문제의 경우 이어지는 경로라고 되어있다. 아래로 내려갈때 대각선 방향의 왼쪽 오른쪽으로만 이동 가능하다.
• DP로 문제를 해결하고자 했다. 문제와는 다르게 반대로 아래에서 위로 왼쪽 오른쪽을 각자 더했을때 더 큰 숫자를 배열에 남기기로 했다.
• 아래에서 위로 비교할때 index가 0보다 작을 경우를 체크하면서 값을 채워나가게 했다.

import java.util.*;
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int[][] dp = new int[triangle.length+1][triangle.length];
        
        for(int i = 1; i<triangle.length+1; i++){
            for(int j = 0; j<triangle[i-1].length; j++){
                for(int k = j-1; k<j+1; k++){
                                        
                    if(k < 0) continue;
                    
                    dp[i][j] = Math.max(dp[i][j], triangle[i-1][j] + dp[i-1][k]);
                    
                    answer = Math.max(dp[i][j], answer);
                }
            }
        }
        
        return answer;
    }
}