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

문제

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

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

풀이

dp 문제로 각 위치마다 최대값을 저장해나간다. 

마지막 행에서 가장 큰 값이 답이된다.

2021.11.08 - [Problem Solving/BOJ] - [BOJ 1932] 정수 삼각형 (Java)

[BOJ 1932] 정수 삼각형 (Java)

 

소스코드

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++){
            for(int j = 0; j <= i; j++){
                dp[i][j] = triangle[i][j];
                if(j == 0){
                    dp[i][j] += dp[i-1][j];
                } else if (j == i){
                    dp[i][j] += dp[i-1][j-1];
                } else {
                    dp[i][j] += Math.max(dp[i-1][j], dp[i-1][j-1]);
                }             
            }
        }
        
        int max = 0; 
        for(int i = 0; i < triangle.length; i++){
            max = Math.max(dp[triangle.length-1][i], max);
        }
        
        return max;
    }
}