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

문제

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

풀이

0. 문제 해석

위 그림처럼 아래부터 올라오면서 누적값을 dp에 저장하고,

아래 인접한 두 칸 중에 누적값이 더 큰 값을 가져와 반복하면서 올라가면 정답을 구할 수 있다.

 

1. 전체 코드

// [프로그래머스] 정수 삼각형 (Java)
import java.util.*;

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

        for(int i = 0; i < size; i++){
            dp[size - 1][i] = triangle[size - 1][i];
        }

        for(int i = (size - 2); i >= 0; i--){
            for(int j = 0; j <= i; j++){
                int cur = triangle[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
                dp[i][j] = cur;
            }
        }

        answer = dp[0][0];
        return answer;
    }
}