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

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

프로그래머스

 

접근 방법

1. 삼각형의 위에서 아래로 이어지는 경로의 값을 더할때, 최대값을 찾는 문제이다.
2. DP가 직관적으로 생각났다.
3. memo배열을 만들고 최대값을 기록하며 이동했고, 가장 아래행 원소의 값을 비교하면된다

코드

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