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

📌 Problem

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 한다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
정수 삼각형 정보가 주어질 때 거쳐간 숫자의 최대합을 구하면 된다.

📌 Solution

대표적인 DP 문제 중에 하나이다. 이중 반복문으로 정수들을 탐색한다. 위에서부터 row = 0, 왼쪽부터 col = 0이라고 할 때 (row, col)의 최대합은 (row, col) + max((row - 1, col - 1), (row - 1, col))이다. 이 때 양끝은 index가 배열을 벗어나지 않도록 주의한다.

📌 Code

public int solution(int[][] triangle) {
    int max = 0;
    for (int r = 1; r < triangle.length; r++)
        for (int c = 0; c < triangle[r].length; c++)
            max = Math.max(max, triangle[r][c] += Math.max(
                    c == 0 ? 0 : triangle[r - 1][c - 1],
                    c == triangle[r].length - 1 ? 0 : triangle[r - 1][c]
            ));
    return max;
}