문제

로직

이 문제는 문제 카테고리에도 있듯이 동적계획법(Dynamic Programming)을 이용하는 문제이다.

삼각형은 무조건 아래보다 길이가 1 작기 때문에 내려갈 때에는 자신과 동일한 인덱스 또는 자신보다 1 큰 인덱스 중 하나를 선택할 수 있다.

맨 아랫줄에서 한 칸 위부터 아래를 반복한다.
자신과 동일한 인덱스와 1 큰 인덱스의 값 중 더 큰 값을 자신에게 더한다.
이를 반복하면 마지막에는 [0][0]의 값에는 제일 큰 값이 존재할 수 있다.

코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int height = triangle.length;
        
        for (int row = height-2; row >= 0; row --) {
            for (int col = 0; col <= row; col ++) {
                triangle[row][col] += Math.max(triangle[row+1][col], triangle[row+1][col+1]);
            }
        }
        
        return triangle[0][0];
    }
}

결과

느낀 점

DP를 알고 나면 쉽게 풀 수 있는 문제로 DP에 대한 기본 개념을 다시 한 번 익힐 수 있는 좋은 문제였던 것 같다.