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

정수 삼각형

풀이

꼭대기에서 바닥으로 내려갈 때 양쪽 아래 대각선으로만 이동 가능하고, 이동 시 값을 더하여 최종적으로 바닥의 최대 값을 찾는 문제이다.
dp를 사용하여 현재 위치에서 이전의 값에서 가져올 수 있는 가장 큰 값을 가져오는 것을 반복하면서 바닥으로 내려가면 결과적으로 최대값을 찾을 수 있다고 판단하였다.

현재 층을 i, 위치를 j라고 할 때, 이전 층 i - 1의 값들 중에서 j - 1 번째의 수와 j번째의 수 중 최대 값을 가져오면 된다. 이때 현재 층의 0번째와 마지막 수 는 더 큰 값을 비교할 필요 없이 이전 층의 첫번째와 마지막을 가져오면 된다.

코드

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