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

출처

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

문제

정수 삼각형이 주어지는데, 항상 오른쪽 아래 또는 왼쪽 아래로만 이동하면서 거쳐간 수의 합의 최대를 구하는 문제이다.

풀이

전형적인 DP문제이므로 DP배열에 기록하면서 내려가면 된다.

삼각형의 두번째 칸부터 왼쪽 위 , 오른쪽 위 둘중 큰 값을 골라 현재 값에 더해주면 최대값을 구할 수 있고 그것을 삼각형의 마지막 까지 반복해서 수행해준다. 그러면 삼각형 마지막 칸에서 가장 큰 숫자가 해답이 될것이다.

Lv3에 있지만 난이도에 맞지 않는 쉬운 문제인것 같다.
여기서 삼각형 양옆 맨 끝 원소들은 범위를 벗어날 수 있으니 isRange()함수를 통해 인덱스를 벗어나는지 검사해주는 로직을 추가하였다.

• 점화식은 아래와 같다.

triangle[i][j] = Math.max(triangle[i-1][j-1],triangle[i-1][j]); 
// 단, index Range 검사 로직이 들어가야함.

코드

import java.util.*;
class Solution {
    
    public boolean isRange(int i, int j) {
        return j >= 0 && j < i+1;
    }
    
    public int solution(int[][] triangle) {
        for(int i = 1; i < triangle.length; i++) {
            for(int j = 0; j < i+1; j++) {
                int x = 0;
                int y = 0;
                if(isRange(i-1, j-1)) {
                    x = triangle[i-1][j-1];
                }
                if(isRange(i-1, j)) {
                    y = triangle[i-1][j];
                }
                triangle[i][j] += Math.max(x, y);
            }
        }
        int answer = Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
        return answer;
    }
}